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