광석 무더기 재편성

어느 광산 회사가 롱 리버(Long River)를 따라 놓인 $N$개의 채굴 지점에서 강모래로부터 희귀 금속을 추출한다. 각 채굴 지점은 강의 발원지로부터의 거리로 구분되며, 채굴 지점마다 광석 한 무더기가 만들어진다.

광석을 모으기 위해 회사는 $N$개의 무더기를 더 적은 수인 $K$개의 무더기로 재편성한다. 재편성된 $K$개의 무더기는 각각 원래의 채굴 지점 중 하나에 놓인다. 무더기를 옮길 때에는 매우 큰 바지선을 사용한다. 바지선은 발원지에서 출발해 하류 방향으로만 이동할 수 있으므로, 채굴 지점 $X$에서 만들어진 무더기는 $Y > X$인 채굴 지점 $Y$로만 옮길 수 있다. 각 무더기는 통째로 다른 채굴 지점으로 옮겨지거나 원래 자리에 그대로 남는다. 무게가 $W$인 무더기를 채굴 지점 $X$에서 $Y$로 옮기는 비용은 $W \times (Y - X)$이며, 옮기지 않은 무더기는 비용에 영향을 주지 않는다. 전체 재편성 비용은 모든 무더기 이동 비용의 합이다.

$N$, $K$, 각 채굴 지점의 위치, 그리고 각 지점에서 만들어진 무더기의 무게가 주어질 때, $N$개의 무더기를 정확히 $K$개의 무더기로 재편성하는 최소 전체 비용을 구하여라.

입력은 여러 개의 테스트 케이스로 이루어지며, 입력의 끝까지 각 테스트 케이스를 처리한다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $K$ ($1 \le K < N \le 1000$)가 주어지며, 각각 초기 무더기의 개수와 재편성 후 원하는 무더기의 개수이다. 이어지는 $N$개의 줄에는 각각 두 정수 $X$와 $W$ ($1 \le X, W \le 10^6$)가 주어지며, 채굴 지점 $X$에서 무게 $W$인 무더기가 만들어졌음을 뜻한다. 한 테스트 케이스 안에서 무더기는 위치 $X$의 강한 증가(순증가) 순서로 주어진다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. $N$개의 무더기를 $K$개의 무더기로 재편성하는 최소 전체 비용이다.