ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Осень — 2018» > задача:


G. Даниил и ряд врагов

Тренировочный турнир сезона «Осень — 2018»

Старт: 06.окт.2018 в 14:00:00
Финиш: 02.ноя.2018 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и Пасха
• B. Даниил и модульные весы
• C. Макс и RLE
• D. Макс и торрент
• E. Макс и мины
• F. Максимальное произведение
• G. Даниил и ряд врагов
• H. Даниил и составление расписания
• I. Даниил и пропавшие результаты
• J. Макс и Medieval
• P1. Таймер: Код доступа
• P10. Таймер: Упаковка конфет в к...
• P2. Таймер: Планирование процес...
• P3. Таймер: Трассировка циклогра...
• P4. Таймер: Мониторинг кратковре...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Даниил и ряд врагов
Даниил и ряд врагов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Битва проходит следующим образом. Герой Даниила вступает в схватку с выбранным врагом, затем (если удалось победить) — со следующим врагом в выбранном направлении, затем (если снова удалось победить) — со следующим, и так до тех пор, пока схватка с очередным врагом не будет проиграна либо не закончатся враги в выбранном направлении.

Герой Даниила выигрывает схватку с врагом, если сила героя строго больше силы врага. Стартовая сила героя Даниила равна $$$M$$$, а после победы над очередным врагом она увеличивается на определённое количество очков.

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

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

Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 2 \cdot 10^5$$$, $$$1 \le K \le 10^9$$$) — соответственно количество врагов и начальная сила героя Даниила.

Вторая строка содержит $$$N$$$ целых чисел $$$A_i$$$ ($$$0 \le A_i \le 10^9$$$) — силу каждого из врагов.

Третья строка содержит $$$N$$$ целых чисел $$$A_i$$$ ($$$0 \le B_i \le 10^9$$$) — прибавка к силе, которую получает герой Даниила после победы над каждым из врагов.

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

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

Примеры

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

Для отправки решений необходимо выполнить вход.

www.contester.ru