가로등 끄기

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

밤새 놀고 난 도브리차는 가로등 중 하나의 바로 옆에서 소등을 시작한다. 각 가로등에는 정해진 소비 전력의 전구가 달려 있으며, 켜져 있는 동안 매초 그만큼의 에너지를 소비한다. 몹시 피곤한 도브리차는 초속 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보다 작다.