Time Limit: 5000 MS Memory Limit: 65536 K
Ever the maturing businessman, Farmer John realizes that he must
manage his time effectively. He has N jobs conveniently numbered
1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning
the barn, mending the fences, and so on).
To manage his time effectively, he has created a list of the jobs
that must be finished. Job i requires a certain amount of time T_i
(1 <= T_i <= 1,000) to complete and furthermore must be finished
by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at
time t=0 and can only work on one job at a time until it is finished.
Even a maturing businessman likes to sleep late; help Farmer John
determine the latest he can start working and still finish all the
jobs on time.
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i
Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of
time, respectively, and must be completed by time 5, 14, 20, and
* Line 1: The latest time Farmer John can start working or -1 if
Farmer John cannot finish all the jobs on time.
Farmer John must start the first job at time 2. Then he can do
the second, fourth, and third jobs in that order to finish on time.