Time Management

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.

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.

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.

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