CF1512F Education

Polycarp 想买一台新电脑，这台电脑的价格为 $c$ 图格里克。为此，他打算在一家大公司找一份程序员的工作。 Polycarp 所在的公司有 $n$ 个职位，编号从 $1$ 开始。处于第 $i$ 个职位的员工每天可以赚取 $a[i]$ 图格里克。职位编号越高，员工获得的图格里克越多。最初，Polycarp 拥有编号为 $1$ 的职位，并且拥有 $0$ 图格里克。 每天，Polycarp 可以选择以下两种操作之一： - 如果 Polycarp 处于第 $x$ 个职位，他可以赚取 $a[x]$ 图格里克。 - 如果 Polycarp 处于第 $x$ 个职位（$x < n$），并且他至少拥有 $b[x]$ 图格里克，那么他可以花费 $b[x]$ 图格里克参加一个在线课程，并晋升到第 $x+1$ 个职位。 例如，若 $n=4$，$c=15$，$a=[1, 3, 10, 11]$，$b=[1, 2, 7]$，那么 Polycarp 可以这样行动： - 第一天，Polycarp 处于第 $1$ 个职位，赚取 $1$ 图格里克。现在他有 $1$ 图格里克； - 第二天，Polycarp 仍处于第 $1$ 个职位，并晋升到第 $2$ 个职位。现在他有 $0$ 图格里克； - 第三天，Polycarp 处于第 $2$ 个职位，赚取 $3$ 图格里克。现在他有 $3$ 图格里克； - 第四天，Polycarp 处于第 $2$ 个职位，并晋升到第 $3$ 个职位。现在他有 $1$ 图格里克； - 第五天，Polycarp 处于第 $3$ 个职位，赚取 $10$ 图格里克。现在他有 $11$ 图格里克； - 第六天，Polycarp 处于第 $3$ 个职位，赚取 $10$ 图格里克。现在他有 $21$ 图格里克； - 六天后，Polycarp 就可以买到新电脑了。 请你计算，Polycarp 至少需要多少天才能买到新电脑。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $c$（$2 \le n \le 2 \cdot 10^5$，$1 \le c \le 10^9$），分别表示公司职位数和新电脑的价格。 每组测试数据的第二行包含 $n$ 个整数 $a_1 \le a_2 \le \ldots \le a_n$（$1 \le a_i \le 10^9$）。 每组测试数据的第三行包含 $n-1$ 个整数 $b_1, b_2, \ldots, b_{n-1}$（$1 \le b_i \le 10^9$）。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示 Polycarp 至少需要多少天才能买到新电脑。

由 ChatGPT 4.1 翻译