Hide

Problem EPizzubestun

Mahjong pizza
It’s Nonni’s birthday and he wants to order his favourite food for everyone at his birthday party, pizza. His favourite pizza place, Mahjong, has a special deal in which you order two large pizzas but only pay for the more expensive of the two.

Nonni has asked his guests what kind of pizza they would like, so he knows how many pizzas need to be ordered.

Nonni wishes to pay as little as possible for the pizzas and asks you for help. Given the pizzas he wishes to order and the price of each pizza you need to figure out which of them to pair together for the special deal to minimize the cost. The pizzas can also be ordered on their own for the listed price. All of the pizzas are large.

Input

The first line of the input contains the integer $n$, the number of pizzas that are to be ordered. The next $n$ lines contain the name of a pizza and a price, separated by a space. The name of each pizza contains only ASCII letters. The price of a pizza is a positive integer less than $10^9$.

Output

Print the minimum price for all the pizzas in the input.

Scoring

 Group Points Constraints 1 50 $1 \leq n \leq 1000$ 2 50 $1 \leq n \leq 10^5$
Sample Input 1 Sample Output 1
4
Prinsinn 2499
Piparinn 2399
Margherita 1899
Pepparinn 2099

4598

Sample Input 2 Sample Output 2
3
Guffi 3099

4998