| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Ежедневно огромное количество людей пользуется электричками. В данной задаче мы рассмотрим направление от станции <<Жилые Мытищи>> (далее ЖМ) до станции <<Большая Центральная>> (далее БЦ). Всего вдоль этого направления находится $n + 1$ станция, при этом станция ЖМ имеет номер $n,ドル а станция БЦ имеет номер 0ドル$. Все пары соседних станций (то есть пары станций с номерами $i$ и $i + 1$) соединены перегонами, при этом никакие другие пары перегонами не соединены.
Каждая электричка стартует в ЖМ и едет в БЦ, при этом на станции номер $i$ ежедневно находятся $c_i$ пассажиров, которые хотят попасть на станцию БЦ. Других пассажиров не бывает, ведь кому придёт в голову ехать не до конечной станции? Для каждого перегона известно количество минут $e_i,ドル за которое его проезжает обычная электричка. Посадка пассажиров на электричку происходит моментально.
Совет директоров компании Российские Стальные Дороги решил пустить экспресс из депо станции <<Жилые Мытищи>> до станции <<Большая Центральная>>. После продолжительных совещаний было решено назвать новый поезд <<Путник>>. На каждом перегоне была построена отдельная колея для нового поезда, и время его проезда от станции $i$ до станции $i - 1$ составляет $p_i$. Как это часто бывает на практике, $p_i$ может быть как меньше $e_i,ドル так и больше.
Поскольку <<Путник>> --- не просто электричка, то ему требуется одна минута на остановку, чтобы бортпроводники провели инструктаж по технике безопасности при поездках на высокоскоростных поездах.
Все пассажиры руководствуются весьма простой логикой: они будут пользоваться новым экспрессом вместо старой электрички, только если это сделает время в пути от их станции до станции 0ドル$ строго меньше. Считается, что пассажир садится в <<Путник>> в самом начале его остановки, то есть тратит минуту на приветствие бортпроводника и прослушивание инструктажа.
Совет директоров хочет максимизировать популярность нового поезда, поэтому они поручили вам выбрать, на каких именно станциях должен останавливаться экспресс, чтобы как можно больше людей им воспользовались. Обратите внимание, что, хотя <<Путник>> стартует из депо станции <<Жилые Мытищи>>, он не обязан остановиться на этой станции.
В первой строке входных данных записано единственное число $n$ (1ドル \leq n \leq 1000$) --- количество перегонов на пути от ЖМ до БЦ.
Во второй строке записаны $n$ целых чисел $e_i$ (1ドル \leq e_i \leq 10^9$) --- время в минутах, за которое электричка проезжает путь от станции $i$ до станции $i - 1$.
В третьей строке содержатся $n$ целых чисел $c_i$ (1ドル \leq c_i \leq 10^9$) --- количество людей, ежедневно пытающихся попасть со станции номер $i$ на станцию 0ドル$.
В четвертой строке написано $n$ чисел $p_i$ (1ドル \leq p_i \leq 10^9$) --- время в минутах, за которое <<Путник>> проезжает перегон между станциями $i$ и $i - 1$ .
В единственной строке выведите одно целое число --- максимально возможное количество пассажиров нового экспресса.
2 1 2 2 2 1 1
0
3 3 2 30 10 100 1 1 2 10
101
В первом примере <<Путник>> доезжает от ЖМ до БЦ на одну минуту быстрее, чем обычная электричка, если не будет делать никаких остановок. Однако если он где-нибудь остановится, то это преимущество пропадёт, и никто не поедет на новом поезде.
Во втором примере экспресс должен делать остановки на станциях 2ドル$ и 3ドル$. Остановиться на станции 1ドル$ он не может, так как это сделает невыгодными поездки со станции 2ドル$.