Lately, there have been false claims that NK doesn't create completely original problems for his contests. To put a stop to these hurtful rumours, he must "negotiate" with the people spreading them. To be exact, his plan is to pay them off, but the structure of the school's society makes it difficult for him to do so without spending too much money.

There are \(N\) individuals at CB, each with a specific price for keeping quiet, \(P_i\), and a relevance value, \(R_i\). To end the rumours for good, NK needs to pay off a group of people with a combined relevance value that is at least half of the total. In other words, the sum of their \(R_i\) values needs to be at least half of the sum of all the \(R_i\) values.

Please help NK find the minimum amount of money he needs to quash the rumours.

Constraints

\(1 \le N \le 5000\)

\(1 \le R_i \le 10^9\)

\(1 \le P_i \le 5000\)

\(\sum_{i=1}^{N} P_i \le 5000\)

Input Specification

The first line will contain one integer \(N\), the number of students at CB. The next \(N\) lines will contain two integers \(P_i\) and \(R_i\), the respective values for the \(i\)-th student

Output Specification

Output the minimum amount of money to stop the rumours.

Sample Input 1

5
1 2
3 4
2 3
5 6
7 10

Sample Output 1

9

Explanation

Paying off students \(3\) and \(5\) results in the minimum cost.

NOTE: The statement to this problem is a joke, and is not meant to be taken literally.