A single printer must process n print jobs, one at a time with no idle time, starting at time 0. Job i takes p_i units of time to print and has a deadline d_i. The printer operator chooses the order in which jobs are printed. If a job finishes printing at time t (i.e. t equals the sum of processing times of all jobs printed at or before it, including itself), its lateness is t - d_i (lateness may be negative if the job finishes before its deadline). Over all possible orderings of the n jobs, find the minimum possible value of the maximum lateness across all jobs.
Input format
Line 1: an integer n.
Next n lines: two integers p_i d_i for job i.
Output format
A single integer: the minimum achievable maximum lateness (it may be negative).
Constraints
- 1 <= n <= 8
- 1 <= p_i <= 20
- 1 <= d_i <= 100