문제
안나는 놀이 공원에서 일하고 있는데, 새로운 롤러 코스터가 다닐 수 있는 철로를 설계하는 일을 맡고 있다.
롤러 코스터 열차의 속도에 영향을 미치는 n곳의 특별 구역을 이미 설계해 놓았는데, 각 구역은 0부터 n−1로 번호가 매겨져 있다.
이제 이 구역들을 모아서 롤러 코스터의 최종 설계를 제안하려고 한다.
문제를 푸는 과정에서, 열차의 길이는 0이라고 가정하자.
0부터 n−1까지 각 i에 대해서, 특별 구역 i는 다음 두 성질을 띠고 있다.
- 이 특별 구역에 진입할 때, 속도 제한이 있다. 열차의 진입 속도는 시속 sikm/h 보다 작거나 같아야 한다.
- 이 특별 구역을 빠져나갈 때, 열차의 속도는 정확히 tikm/h이다. 이 값은 열차가 구역에 진입했을 때 속도와는 상관이 없다.
롤러 코스터의 최종 설계는 n개의 특별 구역을 어떤 순서로 방문하는 단일한 철로 노선이고, 각 n개의 특별 구역을 정확히 한번 지나야 한다.
연속하는 두 특별 구역은 철로로 이어진다.
안나는 n개의 구역을 방문하는 순서를 정하고, 각각의 철로의 길이를 결정해야 한다.
철로의 길이의 단위는 미터이고, 길이는 음이 아닌 정수이다. (0일 수 있다.)
열차가 두 특별 구역을 잇는 철로를 지날 때, 1m를 지날 때마다 속도가 1km/h 감소한다.
열차가 처음 출발할 때, 열차는 안나가 지정한 순서에서 처음에 오는 특별 구역을 1 km/h의 속도로 진입한다.
최종 설계는 다음 요구 사항을 반영해야 한다.
- 열차가 각 특별 구역을 진입할 때, 이 구역의 진입 속도 제한을 어기지 않는다.
- 열차의 속도는 항상 양수이다.
당신은 연속한 특별 구역을 잇는 철로들의 길이의 총합의 최소값을 구해야 한다.
입력
1번 줄 : n
2번 ~ N+1번 줄 : si ti
출력
첫 번째 줄에 연속한 특별 구역을 잇는 철로들의 길이의 총합의 최솟값을 출력한다.
예제1
4
17
43
58
66
3