Dr.Kong has entered a bobsled competition because he hopes his hefty weight will give his an
advantage
over the L meter course (2 <= L<= 1000).
Dr.Kong will push off the starting line at 1 meter per second, but his speed can change while he
rides
along the course. Near the middle of every meter Bessie travels, he can change his speed
either by
using gravity to accelerate by one meter per second or by braking to stay at the same speed or
decrease
his speed by one meter per second.
Naturally, Dr.Kong must negotiate N (1 <= N <= 500) turns on the way down the hill. Turn i is
located
T_i meters from the course start (1 <= T_i <= L-1), and he must be enter the corner meter at
a peed of at most S_i meters per second (1 <= S_i <= 1000).
Dr.Kong can cross the finish line at any speed he likes.
Help Dr.Kong learn the fastest speed he can attain without exceeding the speed limits on the
turns.
Consider this course with the meter markers as integers and the turn speed limits in brackets
(e.g., '[3]'):
0 1 2 3 4 5 6 7[3] 8 9 10 11[1] 12 13[8] 14
(Start) |------------------------------------------------------------------------------------- ---------à|
(Finish)
Below is a chart of Dr.Kong 's speeds at the beginning of each meter length of the course:
Max: [3] [1] [8]
Mtrs: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Spd: 1 2 3 4 5 5 4 3 4 3 2 1 2 3 4
His maximum speed was 5 near the beginning of meter 4.
Line 1:Two space-separated integers:LandN
Lines 2..N+1:Line i+1 describes turn i with two space-separatedintegers:T_iandS_i
Line 1:A single integer Line 1: A single integer, representing the maximum speed which Dr.Kong can attain between
the start and the finish line, inclusi
14 3 7 3 11 1 13 8
5