Defuse the Bombs

You can defuse only one bomb at a time and cannot interrupt it. Bomb i takes X[i] time and must be finished at or before time Y[i]. Time starts at 0. Find the minimum total time to defuse all bombs; if it is impossible, output −1.

This site has made the standard input and output explicit.

输入格式

The first line contains n, followed by n lines of duration deadline. 1≤n≤200000; the source gives no time bounds, so on this site 1≤duration≤10⁹ and 1≤deadline≤10¹⁵.

输出格式

Output one integer, the answer.

样例 1

输入：

5
2 4
1 9
1 8
4 9
3 12

输出：

11

样例 2

输入：

2
2 2
1 2

输出：

-1

样例 3

输入：

1
3 3

输出：

3

样例说明

Example 1: scheduling by deadline, the cumulative completion times 2, 3, 4, 8, 11 are all on time, so output 11. Example 2: the total time is 3, but both must be finished before 2, so output −1. Example 3: the work finishes exactly at deadline 3, so output 3.