← 返回题目列表

Codeforces · 1512/F

F. 教育

中文机器翻译题面 查看原题

Polycarp 想买一台新电脑,价格为 $$$c$$$ 图格里克。为此,他想在一家大公司找到一份程序员的工作。

Polycarp的公司有$$$n$$$个职位,编号从1开始。职位为 $$$i$$$ 的员工每天赚取 $$$a[i]$$$ 图格里克。职位编号越高,员工获得的图格里克就越多。最初,Polycarp 获得的职位编号为 $$$1$$$,并拥有 $$$0$$$ 图格里克。

波利卡普每天可以做以下两件事之一:

- 如果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$$$-st 位置并赚取 $$$1$$$ tugrik。现在他有$$$1$$$ tugrik;
- 第二天,Polycarp 位于 $$$1$$$-st 位置,并移至 $$$2$$$-nd 位置。现在他有$$$0$$$图格里克;
- 第三天,Polycarp 处于 $$$2$$$-nd 位置并赚取 $$$3$$$ 图格里克。现在他有$$$3$$$图格里克;
- 第四天,Polycarp 处于 $$$2$$$-nd 位置,并被转移到 $$$3$$$-rd 位置。现在他有$$$1$$$图格里克;
- 第五天,Polycarp 处于 $$$3$$$-rd 位置并赚取 $$$10$$$ 图格里克。现在他有 $$$11$$$ 图格里克;
- 第六天,Polycarp 处于 $$$3$$$-rd 位置并赚取 $$$10$$$ 图格里克。现在他有 $$$21$$$ 图格里克;
- 六天后,波利卡普可以给自己买一台新电脑。

求 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 能够购买新计算机的最短天数。

示例

输入 #1

3
4 15
1 3 10 11
1 2 7
4 100
1 5 10 50
3 14 12
2 1000000000
1 1
1

输出 #1

6
13
1000000000