가로등 끄기

시간 제한1초메모리 제한128 MB

요약

직선 위에 놓인 램프들의 위치와 소비 전력이 주어졌을 때, 출발 위치에서 시작해 모든 램프를 끄는 데 드는 총 에너지를 최소화하는 이동 순서를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

도브리차는 새롭고 보수도 좋은 일자리를 얻었다. 매일 아침 그는 마을의 모든 가로등을 꺼야 한다. 가로등은 모두 곧게 뻗은 길의 한쪽에 일렬로 서 있다.

밤새 놀고 난 도브리차는 가로등 중 하나의 바로 옆에서 소등을 시작한다. 각 가로등에는 정해진 소비 전력의 전구가 달려 있으며, 켜져 있는 동안 매초 그만큼의 에너지를 소비한다. 몹시 피곤한 도브리차는 초속 1미터로 걷고, 가로등을 지나치는 순간 곧바로 끈다(끄는 데 추가 시간은 들지 않는다).

모든 가로등은 도브리차가 그 앞에 도착하는 순간까지 계속 에너지를 소비한다. 가로등들의 위치, 각 전구의 소비 전력, 그리고 도브리차가 처음 서 있는 가로등이 주어질 때, 모든 가로등을 끄기까지 소비되는 총 에너지의 최솟값을 구하여라.

입력

첫째 줄에 가로등의 개수 N (2 ≤ N ≤ 1000)이 주어진다.

둘째 줄에 도브리차가 처음 서 있는 가로등의 번호 V (1 ≤ V ≤ N)가 주어진다.

이어지는 N개의 줄에는 각 가로등의 정보가 두 정수 D와 W (0 ≤ D ≤ 1000, 0 ≤ W ≤ 1000)로 주어진다. D는 마을의 시작점으로부터 가로등까지의 거리(미터)이고, W는 그 전구의 소비 전력, 즉 1초 동안 소비하는 에너지의 양이다. 가로등은 D가 감소하지 않는 순서로 정렬되어 주어진다.

출력

모든 가로등을 끄는 데 소비되는 총 에너지의 최솟값을 한 정수로 출력한다. 정답은 항상 1,000,000,000보다 작다.

예제3

예제 1
입력
```
3
2
1 4
6 5
9 7
```
예상 출력
```
65
```
예제 2
입력
```
4
3
2 2
5 8
6 1
8 7
```
예상 출력
```
56
```

예제 3

입력

예상 출력