당신은 N개의 섬으로 구성된 한 공원을 방문하고 있다. 모든 섬에는 어느 섬으로든 이어진 다리가 정확하게 하나씩 있다. i째 섬에서 외부로 나가는 다리의 길이를 Li라고 하자. 따라서 공원에는 N개의 다리가 존재하는 셈이다. 물론 다리는 양방향으로 모두 통행 가능하다.

이 공원에서는 입장할 때 페리를 정확히 한대를 대여해준다. 페리는 아무 섬에서 아무 섬으로나 원하는 대로 이용할 수 있다.

하지만 당신은 페리를 타는 것보다 걷는 것을 더 좋아한다. 그렇기 때문에 공원을 순회하면서 다리를 따라 걷는 거리를 최대화하고 싶어한다.

하지만, 페리는 단 한대이기 때문에 다음과 같은 규칙을 만족하며 공원을 순회하고자 한다.

• 순회의 시작은 당신이 원하는 아무 섬에서나 하면 된다. 단, 순회의 시작 지점에 페리를 정박해놨기 때문에 반드시 처음 지점으로 되돌아와야 한다.
• 들른 적이 있는 섬을 또 거쳐서는 안 된다. (단, 순회의 시작은 제외)
• 다리를 이용해 섬을 방문하는 경우 당신이 걸은 전체 거리에 다리의 길이가 더해진다.

입력

• 첫째 줄에는 공원에 있는 섬의 수 N이 들어있다. 섬들은 1 이상 N 이하 범위인 번호로 식별한다. (2 ≤ N ≤1,000,000)
• 다음 N 줄에는 다리에 대한 정보가 있다. i째 줄에는 i째 섬에 달려 있는 다리가 연결하는 다른 섬의 번호와 이 다리의 길이 Li가 순서대로 공백 사이에 들어있다. 자기 자신을 가리키는 다리는 없으며 다리의 시작점과 끝점은 항상 서로 다르다. (1 ≤ Li ≤ 100,000,000)

출력

입출력 예

입력

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

출력

19

입출력 보충

• 1번 섬에서 출발한다.
• 길이가 8인 다리를 이용해 3번 섬으로 간다.
• 길이가 2인 다리를 이용해 4번 섬으로 간다.
• 길이가 4인 다리를 이용해 1번 섬으로 간다.
• 1번 섬에서 2번 섬까지는 페리를 이용한다.
• 길이가 3인 다리를 이용해 7번 섬으로 간다.
• 길이가 2인 다리를 이용해 2번 섬으로 간다.

출처:Fate