eolymp
bolt
Try our new interface for solving problems
Məsələlər

Черепаха

Черепаха

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Домик черепахи расположен в начале прямой узкой грядки, на которой должны прорасти одуванчики – ее любимое лакомство. И вот черепахе приснился вещий сон. Из него она узнала, что наконец-то после полуночи начнут расти одуванчики. Ей даже приснилось, в какой момент времени и в какой точке грядки вырастет каждый одуванчик. Ровно в полночь черепаха выползла из домика, чтобы съесть все одуванчики и до следующей полуночи вернуться домой.

Черепаха может ползти со скоростью, не превосходящей величины v_max. Одуванчик она съедает, остановившись на время d. Если одуванчик начать есть, но не доесть до конца, то он засыхает, поэтому его надо съедать за один прием. Одуванчики прорастают тем позже, чем дальше они расположены от начала грядки. В одной точке не могут прорастать несколько одуванчиков, а также несколько одуванчиков не могут прорастать в один момент времени.

Требуется определить, в какой момент времени черепаха сможет вернуться домой, съев все одуванчики и затратив на путешествие наименьшее время.

Giriş verilənləri

В 1-й строке входного файла находятся 2 целых числа, разделенные пробелом: v_max (в см/мин) и d (в минутах).

(0 < v_{max }≤ 200, 0d500)

Во 2-й строке находится число N – количество одуванчиков (в штуках). 0N1400 при d= 0, в противном случае 0N200.

В каждой из последующих N строк расположены: целое число x_i – расстояние от одуванчика до начала грядки (в сантиметрах), 0x_i_{ }32767, и через пробел t_i – момент прорастания одуванчика (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Входные данные гарантируют, что черепаха может съесть все одуванчики и вернуться домой в течение суток.

Çıxış verilənləri

Выходной файл должен содержать момент времени возвращения черепахи домой (в формате hh:mm), округленный до целых минут в большую сторону.

Nümunə

Giriş verilənləri #1
3 1 
1
100 00:01
Çıxış verilənləri #1
01:08