시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 787 142 98 36.296%

문제

연구소에서 “초 울트라 캡쑝 으라차 마징가 Z”(이하 마징가)를 완성했다. 하지만 지구는 이미 태권 V로 인해 평화로운 상태를 유지하고 있기 때문에 마징가는 동네에서 가로등을 끄는 일을 시키기로 했다.

마을의 중심에는 매우 긴 도로가 있는데, 이 도로 변에는 가로등이 세워져 있다. 마징가는 이 가로등을 매일 새벽 5시에 끄기 시작해야 한다. 새벽 5시 정각에 마징가는 정확히 여러 가로등 중에서 어느 한 가로등 바로 밑에 위치하고 있다가 일을 시작한다. 그런데, 가로등에는 일정량의 전력을 소비하는 전구가 달려있고, 우리의 날쌘돌이 마징가는 절약정신이 매우 투철하기 때문에 쓸데없이 전력을 낭비하길 원치 않는다.

그래서 소비전력을 최소화할 수 있도록 가로등을 끄는 순서를 알아내고 싶어 한다. 마징가는 일정하게 1m/sec 의 속도로 움직이며, 가로등을 끈 동안의 시간은 무시해도 된다. 왜냐하면 마징가는 너무 날쌔기 때문에 지나가면서 순식간에 가로등을 끌 수 있기 때문이다.

그렇다면, 절약정신으로 똘똘 뭉쳐진 우리의 날쌘돌이 마징가를 도와줄 수 있는 프로그램을 작성하시오.

가로등의 위치와 그 가로등이 소비하는 전력의 양이 주어져 있을 때, 5시 정각이후에 낭비될 수 있는 전력의 최소값을 구하면 된다.

입력

첫째 줄에는 2개의 정수 N(1≤N≤1,000), M 이 있다. 첫 번째 정수 N 은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M 은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가로등에 관한 두 개의 정수가 입력된다. 첫 번째 정수 D 는 가로등의 위치를 나타내고, 두 번째 정수는 이 가로등의 전력소비량 W 을 나타낸다. 가로등의 위치는 마을이 시작되는 부분부터의 거리를 나타내며, 전력소비량은 1초당 소비되는 전력량을 나타낸다. 그러므로, 어떤 가로등의 전력소비량이 w 이고, 이 가로등이 s 초 동안 켜져 있는 동안에 소비된 전력량은 ws 가 된다. 가로등은 위치를 나타내는 정수 D 의 오름차순으로 입력된다. 같은 줄에 나타나는 정수들 사이에는 하나의 space 가 있다. 가로등 번호는 입력되는 순서대로 1번, 2번, ..., N 번을 부여한다.

단, 낭비되는 전력의 최소값이 1,000,000,000 보다는 항상 작은 데이터가 입력된다.

출력

첫 줄에 낭비되는 전력의 최소값을 나타내는 정수를 출력한다.

예제 입력

6
5
3 2
11 10
12 18
13 19
15 15
17 19

예제 출력

370

힌트