가로등 끄기

긴 도로 위에 N개의 가로등이 위치 순서대로 서 있다. 각 가로등은 켜져 있는 동안 초당 일정한 전력을 소비한다. 시각 0에 로봇은 M번 가로등 바로 아래에 있으며, 그 가로등은 즉시 끌 수 있다.

로봇은 초속 1m로 이동하고, 가로등을 끄는 데 걸리는 시간은 0이라고 본다. 어떤 가로등이 시각 t에 꺼지고 그 가로등의 소비 전력이 W라면, 그 가로등 때문에 낭비된 전력은 W × t이다.

모든 가로등을 끌 때까지 낭비되는 전력의 총합이 최소가 되도록 이동 순서를 정하라. 그 최솟값을 출력한다.

첫째 줄에 두 정수 N과 M이 주어진다. N은 가로등의 개수이고, M은 로봇이 처음 서 있는 가로등의 번호이다.

다음 N개의 줄에는 각 가로등의 위치 D와 초당 전력 소비량 W가 주어진다. D는 도로가 시작되는 지점으로부터의 거리이며, 0 ≤ D ≤ 1,000이다. W는 1 ≤ W ≤ 100,000,000을 만족한다.

가로등은 위치 D의 오름차순으로 입력되며, 입력 순서대로 1번부터 N번까지 번호가 붙는다. 1 ≤ N ≤ 1,000이다.

낭비되는 전력의 최솟값은 항상 1,000,000,000보다 작다.

낭비되는 전력의 최솟값을 나타내는 정수 하나를 출력한다.