F. Образование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп мечтает о покупке нового компьютера, который стоит $$$c$$$ тугриков. Для этого он хочет устроиться программистом в большую компанию.

В компании Поликарпа есть $$$n$$$ должностей, пронумерованных начиная с единицы. Сотрудник на должности $$$i$$$ каждый день зарабатывает $$$a[i]$$$ тугриков. Чем выше номер должности, тем больше тугриков получает сотрудник. Изначально Поликарп устраивается на должность с номером $$$1$$$ и имеет $$$0$$$ тугриков.

Каждый день Поликарп может сделать одно из двух действий:

  • Если Поликарп находится на должности $$$x$$$, то он может заработать $$$a[x]$$$ тугриков;
  • Если Поликарп находится на должности $$$x$$$ ($$$x < n$$$) и имеет хотя бы $$$b[x]$$$ тугриков, то он может потратить $$$b[x]$$$ тугриков на онлайн-курс и перейти на должность $$$x+1$$$.

Например, если $$$n=4$$$, $$$c=15$$$, $$$a=[1, 3, 10, 11]$$$, $$$b=[1, 2, 7]$$$, то Поликарп может действовать так:

  • В первый день Поликарп находится на должности $$$1$$$ и зарабатывает $$$1$$$ тугрик. Теперь у него есть $$$1$$$ тугрик;
  • Во второй день Поликарп находится на должности $$$1$$$ и переходит на должность $$$2$$$. Теперь у него есть $$$0$$$ тугриков;
  • В третий день Поликарп находится на должности $$$2$$$ и зарабатывает $$$3$$$ тугрика. Теперь у него есть $$$3$$$ тугрика;
  • В четвертый день Поликарп находится на должности $$$2$$$ и переходит на должность $$$3$$$. Теперь у него есть $$$1$$$ тугрик;
  • В пятый день Поликарп находится на должности $$$3$$$ и зарабатывает $$$10$$$ тугриков. Теперь у него есть $$$11$$$ тугриков;
  • В шестой день Поликарп находится на должности $$$3$$$ и зарабатывает $$$10$$$ тугриков. Теперь у него есть $$$21$$$ тугриков;
  • Спустя шесть дней, Поликарп может купить себе новый компьютер.

Найдите минимальное количество дней, через которое Поликарп сможет купить себе новый компьютер.

Входные данные

В первой строке содержится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество дней, через которое Поликарп сможет купить себе новый компьютер.

Пример
Входные данные
3
4 15
1 3 10 11
1 2 7
4 100
1 5 10 50
3 14 12
2 1000000000
1 1
1
Выходные данные
6
13
1000000000