Codeforces Round 713 (Div. 3) |
---|
Закончено |
Поликарп мечтает о покупке нового компьютера, который стоит $$$c$$$ тугриков. Для этого он хочет устроиться программистом в большую компанию.
В компании Поликарпа есть $$$n$$$ должностей, пронумерованных начиная с единицы. Сотрудник на должности $$$i$$$ каждый день зарабатывает $$$a[i]$$$ тугриков. Чем выше номер должности, тем больше тугриков получает сотрудник. Изначально Поликарп устраивается на должность с номером $$$1$$$ и имеет $$$0$$$ тугриков.
Каждый день Поликарп может сделать одно из двух действий:
Например, если $$$n=4$$$, $$$c=15$$$, $$$a=[1, 3, 10, 11]$$$, $$$b=[1, 2, 7]$$$, то Поликарп может действовать так:
Найдите минимальное количество дней, через которое Поликарп сможет купить себе новый компьютер.
В первой строке содержится одно целое число $$$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
Название |
---|