Turtle#669
The turtle's home is at the beginning of a straight, narrow garden bed where her favorite food—dandelions—will sprout. One night, the turtle had a prophetic dream: she learned that the dandelions would begin to grow after midnight. She even dreamed of the exact time and place on the bed where each dandelion would appear. Exactly at midnight, the turtle left her home to eat all the dandelions and return home by the next midnight.
The turtle can crawl at a speed no greater than v_{max} (in cm/min). She eats a dandelion by stopping for minutes. If she starts eating a dandelion but does not finish, it will wither; so, each dandelion must be eaten at once. The farther away the dandelion is from the start, the later it sprouts. No two dandelions sprout at the same place or at the same time.
Your task is to determine the earliest possible time the turtle can return home after eating all the dandelions, minimizing the total journey time.
The first line contains two integers separated by a space: v_{max} (in cm/min) and (in minutes).
0 < v_{max} \leq 200, 0 \leq d \leq 500
The second line contains — the number of dandelions. 0 \leq N \leq 1400 if d = 0, otherwise 0 \leq N \leq 200.
Each of the next lines contains: an integer x_i — distance from the start (in centimeters), 0 \leq x_i \leq 32767, followed by a space and t_i — the sprouting time (in format). The pairs are given in order of increasing distance.
The input guarantees that the turtle can eat all the dandelions and return home within one day.
Print the time the turtle returns home (in format), rounded up to the nearest whole minute.
Example 1