Pizzubestun

Mahjong 피자

Nonni는 생일을 맞아 파티에 참석한 모두를 위해 자신이 가장 좋아하는 음식인 피자를 주문하려 한다. 그가 가장 좋아하는 피자 가게 Mahjong에는 ``두 개 묶음 할인''이라는 행사가 있다. 이 행사에서는 메뉴에 있는 대형 피자 2개를 주문할 수 있지만, 그중 더 비싼 피자의 가격만 지불한다.

Nonni는 손님들에게 어떤 피자를 원하는지 이미 물어보았으므로, 몇 개의 피자를 주문해야 하는지와 어떤 피자를 주문해야 하는지 알고 있다.

Nonni는 피자에 가능한 한 적은 돈을 쓰고 싶어 하며, 당신에게 도움을 요청한다. 그가 주문하려는 피자들과 각 피자의 가격이 주어질 때, 비용을 최소화하려면 두 개 묶음 할인으로 어떤 피자들을 서로 짝지어야 하는지 알아내야 한다(피자를 낱개로 주문할 수도 있다).

점수

그룹 | 점수 | 제한

1 | 50 | $1 \leq n \leq 1000$

2 | 50 | $1 \leq n \leq 10^5$

첫 번째 줄에는 주문해야 하는 피자의 수 $n$이 주어진다. 다음 $n$개의 줄에는 피자의 이름과 가격이 공백으로 구분되어 주어진다. 각 피자의 이름은 ASCII 문자로만 이루어져 있다(숫자는 포함하지 않는다). 각 피자의 가격은 항상 양의 정수이며 $10^9$보다 작다.

이 주문의 가능한 최소 가격을 출력한다.