Time Management

Interview

Time limit2sMemory limit128 MB

Summary
Given tasks with durations and deadlines, find the latest single start time so that all tasks scheduled back to back meet their deadlines, or report -1 if impossible.
Level

Medium4 of 10

Topics
Greedy, Sorting, Prefix sum
Solved
No attempts yet

Problem

After becoming a camp assistant, Jinyoung realized that he needed to manage his time efficiently. He has N tasks to do in one day, numbered from 1 to N.

Each task i takes exactly T_i hours to complete and must be finished no later than time S_i. Jinyoung can start working at time 0, and he cannot work on two or more tasks at the same time.

Jinyoung wants to sleep in as long as possible. Find the latest time he can start working while still completing every task by its deadline.

Input

The first line contains the number of tasks N.

Each of the next N lines contains two integers T_i and S_i for the i-th task.

Output

Print the latest time at which Jinyoung can start working and still finish every task by its deadline.

If he cannot finish all tasks even when starting at time 0, print -1.

Constraints

  • 1 <= N <= 1,000
  • 1 <= T_i <= 1,000
  • 1 <= S_i <= 1,000,000

Examples1

  1. Example 1

    Input
    4
3 5
8 14
5 20
1 16
    Expected output
    2