대학교 첫 방학을 맞이한 명우는 농촌활동을 갔다. 명우가 간 곳은 전라남도 해남, 감자밭이다. 그 곳은 1년에 두 번 농사를 지어 지금이 감자 수확기다. 열심히 감자 수확을 하던 중 갑자기 비가 오기 시작했다. 수확한 감자 포대를 비에 방치해두면 결국 썩어버리기 때문에 여러 곳에 퍼져 있는 감자 포대를 K 개의 지점에 나눠 모아 비닐로 감싸려고 한다.

밭을 1차원 직선으로 볼 수 있고, 감자 포대를 하나의 점으로 볼 수 있다. 그러면 감자 포대의 위치를 x 좌표로 표현할 수 있다. i 번째 감자 포대의 위치는 xi 이고 무게는 wi 이다.

이제 명우는 각 감자 포대들을 옮겨야하는데, 옮길 때 드는 힘든 정도를 (이동거리)× 무게라고 하자. 우리는 감자 포대 모으는 위치들을 적절히 잘 정하여, 각 감자 포대들을 모두 옮 길 때 드는 힘든 정도의 합을 최소화하려고 한다. 그 때 힘든 정도의 합의 최솟값을 구하여라.

입력

• 첫 줄에 감자 포대들의 개수 N 과 모을 지점의 개수 K 가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ K ≤ 30)
• 그 다음 N 개의 줄에 각 감자 포대의 위치 값 xi 와 무게 wi 가 주어진다. (xi,wi 는 정수, |xi| ≤ 100,000 , 0 < wi ≤ 1000)

출력

입출력 예

입력

6 3
5 2
6 5
12 6
19 4
20 1
27 3

출력

27

힌트

출처: KOI 전국본선대비 모의고사(전명우) 2012년 7월 10일