@operator12

Петя решил отправиться в путешествие.Сейчас он едет в поезде.Поезд состоит из n вагонов, длина i-го вагона - ai метров.Расстоянием между вагонами можно пренебречь.
Петя заметил, что в некоторых вагонах включен свет.Поезд приближается к железнодорожному туннелю длинной h метров.Петя не хочет, чтобы в некоторый момент времени в туннеле оказались только вагоны, в которых не горит свет.Петя называет темным момент времени, если во всех вагонах,некоторый участок ненулевой длинны которых находится в туннеле,не горит свет.Чтобы исключить появление такого момента, Петя хочет включить свет в некоторых вагонах.

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

Формат входных данных:

Входные данные содержат несколько тестовых примеров. Первая строка содержит одно число t (1 ≤ t ≤ 100) –— количество тестов. Далее следуют описания тестов.

Каждый тест задается следующим образом: первая строка содержит два натуральных числа n, h (1 ≤ n ≤ 105, 1 ≤ h ≤ 109) — количество вагонов в поезде и длину туннеля в метрах. Следующая строка теста содержит n натуральных чисел ai (1 ≤ ai ≤ 109) — длины вагонов в метрах. Следующая строка содержит n чисел, i-е из который равно 1, если в i-м вагоне изначально включен свет, и 0 в противном случае. Вагоны перечислены от головы к хвосту поезда.

Сумма значений n по всем тестам не превышает 106.

Формат выходных данных:

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

Примеры:

Входные данные
2
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
5 2
1 2 3 1 1
1 1 0 1 1

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

0

@SuperKir

Смотри по длинам вагонов, если она превышает длину туннеля - включай свет.
Ну и естественно начало/конец вагонов надо осветить.

Т.е.:
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
Здесь:
1. Начало есть.
2. Пошло отсутствие света, но длина вагона 3, а туннеля 10, нормас.
3. Пошло отсутствие света, но длина вагонов уже 3+4 = 7, а туннеля 10, пойдет.
4. Пошло отсутствие света, но длина вагонов уже 3+4+5 = 12, а туннеля 10, не пойдет, включаем в крайнем свет. Включений = 1.
5. Свет есть.
6. Пошло отсутствие света, но длина вагона 9, туннеля 10, можно.
7. Пошло отсутствие света, но длина вагона 9+9 = 18, туннеля 10, не прокатит + еще и крайний. Включений = 2.

5 2
1 2 3 1 1
1 1 0 1 1
Тут по аналогии, в 3 света нет, длина туннеля меньше вагона, значит включение = 1.

0

@Kuzia domovenok

где делают такие вагоны, чтобы все разной длины?

0

@SuperKir

Kuzia domovenok, в задачках

0