Problem E
Pizzubestun
Languages
en
is
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 BaraDodlur 2899 Margherita 1899 |
4998 |
