광석 더미 모으기

어느 광산 회사가 강모래에서 테르븀을 캔다. 테르븀은 가벼운 자석을 만드는 데 쓰이는 희귀 금속이다. 회사는 긴 강을 따라 놓인 채굴 지점 $N$곳에서 작업하고, 각 지점은 강 발원지로부터의 거리로 구분한다. 채굴 지점마다 양은 많지 않지만 값이 비싼 광석 더미가 하나씩 나온다.

광석을 실어 내려고 회사는 이 $N$개의 더미를 더 적은 수인 $K$개의 더미로 모은다. 새로 만든 더미는 모두 원래 채굴 지점 중 한 곳에 놓이고, 트럭이 와서 실어 간다.

더미를 옮기는 데는 바지선을 쓴다. 바지선은 아주 커서 광석을 얼마든지 실을 수 있다. 바지선은 발원지에서 출발해 하류 방향으로만 움직이므로, 채굴 지점 $X$에서 나온 더미는 $Y > X$인 채굴 지점 $Y$로만 옮길 수 있다. 각 더미는 통째로 다른 지점으로 옮기거나 제자리에 그대로 둔다. 무게가 $W$인 더미를 지점 $X$에서 지점 $Y$로 옮기는 비용은 $W \times (Y - X)$이다. 재배치의 총비용은 더미마다 옮긴 비용을 모두 더한 값이고, 옮기지 않은 더미는 총비용에 영향을 주지 않는다.

$N$과 $K$, 채굴 지점 $N$곳의 위치, 각 지점에서 나온 더미의 무게가 주어질 때, 처음 $N$개의 더미를 $K$개의 더미로 모으는 최소 총비용을 구하는 프로그램을 작성하시오.

첫째 줄에 처음 더미의 개수 $N$과 재배치 후 남길 더미의 개수 $K$가 공백으로 구분되어 주어진다 ($1 \le K < N \le 1000$).

다음 $N$개의 줄에는 각 더미의 정보가 두 정수 $X$와 $W$로 주어진다. 채굴 지점 $X$에서 무게 $W$인 더미가 나왔다는 뜻이다 ($1 \le X, W \le 10^6$). 더미는 채굴 지점의 좌표가 엄격히 증가하는 순서로 주어진다.

처음 $N$개의 더미를 $K$개의 더미로 모으는 최소 총비용을 정수 하나로 한 줄에 출력한다.