This problem was featured from DMOJ's Wesley Anger Contest 4 and has been transferred to this site. The time limit has been rescaled by a factor of 2 from the official time limit. If there are any concerns regarding a specific problem's time limit, please contact the administrators. Due to these changes, some of these problems may not be doable in specific languages due to the time limit cap.

The squirrel nation is holding a (totally not rigged) election! There are only two candidates in this election: Wesley and Wesley Besley. To reign supreme over the nation, Wesley will do anything to make sure he wins.

The nation is split into \(N\) provinces, with the \(i^{th}\) province populated by \(v_i\) voters. If Wesley earns more than half of the votes in the \(i^{th}\) province he is awarded with \(p_i\) points, otherwise Besley will automatically get the \(p_i\) points. After the voting process, whichever candidate earns the most points in the end wins (ties do not count as a victory). Every squirrel must cast a vote for either of the candidates.

As a very influential candidate, Wesley can force any number of voters to vote for him. Assuming every voter in the nation initially planned to vote for Besley, what is the minimum amount of voters Wesley needs in order to win the election?

For this problem, Python users are recommended to use PYPY over CPython.

Constraints

For this problem, you will NOT be required to pass all the samples to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

\(1 \le N \le 5\,000\)
\(1 \le v_i \le 10^9\)
\(0 \le p_i \le 5\,000\)
The total sum of \(p_i\) is at least \(1\) and at most \(5\,000\).

Subtask 1 [20%]

\(v_i = 1\)

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer \(N\) indicating the number of provinces in the squirrel nation.

The next \(N\) lines each contain two integers \(v_i\) and \(p_i\) separated by a space.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

On a single line, output an integer representing the minimum amount of voters Wesley needs.

Sample Input 1

5
1 5
1 8
1 0
1 1
1 2

Sample Output 1

2

Sample Explanation 1

By forcing a victory with the first two provinces, Wesley can instantly gain \(13\) points and win the election. Note that \(8\) points will result in a tie, which will not be enough.

Sample Input 2

6
4 5
9 8
1 0
1 1
1 2
3 4

Sample Output 2

6

Sample Explanation 2

By forcing a victory with the first, fifth, and sixth provinces, Wesley can win the election by threatening \(3 + 1 + 2 = 6\) voters.