| Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Пешеход переходит дорогу, состоящую из K полос автомобильного движения. Он заметил N автомобилей, каждый из которых движется по своей полосе движения wi и пересечет место перехода дороги через bi секунд. Пешеход НЕ может останавливаться между полосами дороги. Он может остановиться только у одного из краев дороги. Если же он находится на разграничителе полос, то он обязан переходить одну из соседних полос, то есть двигается вперед или назад. При этом, если он уже начал переходить полосу, то он не может остановиться и пересечение очередной полосы движения займет у него время t.
В начальный момент времени пешеход находится на краю дороги, ближайшая к которому полоса имеет номер 1. Дорога считается бесконечной в обе стороны. Пешеход может двигаться только по прямой, перпендикулярной дороге, то есть, он идет или ждет на одном из краев дороги, или идет прямо, или назад. Найдите минимальное время, за которое пешеход может перейти дорогу (пересечь все ее полосы движения) и не оказаться сбитым машиной. Пешеход считается сбитым машиной i, если момент времени bi он оказался на полосе wi. Но если он в это время находился между полосами или в начале и в конце пути, то машина его не задевает.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|