시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB222100.000%

문제

두 명의 등산가가 있다. 두 사람은 봉우리가 N개 있는 산의 양쪽 끝에 각각 서있고 서로 반대편에 도달해야한다. 하나의 특수한 조건은 두 명의 등산가가 서로 산을 넘어 반대편으로 갈 때 같은 시각에 같은 높이에 있어야 한다는 것이다. 즉, 두 명의 높이를 항상 같도록 유지하며 서로 산을 넘어야한다. 산을 넘을 때 두 명이 이동한 높이의 합의 최솟값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 봉우리의 수 N(3 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에 봉우리의 번호와 그 봉우리의 높이가 주어진다. 시작위치의 높이는 같으며 시작과 끝을 제외하고 같은 높이의 봉우리는 없다. 중간 봉우리가 시작위치보다 낮은 경우는 없다. 봉우리의 번호는 1부터 N까지 순서대로 매겨져 있고, 높이는 2,000 이하의 음이 아닌 정수이다. 입력은 봉우리 번호가 증가하는 순서로 주어진다. 

출력

첫째 줄에 두 명이 이동한 높이의 합의 최솟값을 출력한다.

예제 입력 1

3
1 0
2 5
3 0

예제 출력 1

20

예제 입력 2

5
1 0
2 10
3 5
4 15
5 0

예제 출력 2

100

예제 입력 3

7
1 10
2 15
3 11
4 20
5 12
6 14
7 10

예제 출력 3

120