크리스마스 이브

산타 코퍼레이션은 크리스마스 이브 밤부터 크리스마스 새벽까지 전 세계 어린이에게 선물을 배달한다. 배송에 자원한 산타는 하이테크 썰매를 한 대씩 받고, 이 썰매의 트렁크는 물품관리부 창고 한 곳과 순간이동기로 연결된다. 창고 한 곳에는 순간이동기를 한 대만 설치할 수 있어서 썰매 한 대마다 창고가 하나씩 필요하다.

물품관리부는 일직선 위에 놓인 창고 $n$개를 관리한다. 이 중에서 순간이동기를 설치할 창고 $k$개를 고르고, 선택되지 않은 창고의 선물은 모두 선택된 창고로 옮겨야 한다.

$i$번 창고는 위치 $x_i$에 있고 선물 $w_i$톤이 들어 있다. 한 창고의 선물은 쪼갤 수 없어서 한 번에 전부 다른 창고 한 곳으로 옮긴다. 위치 $x_i$의 창고에서 위치 $x_j$의 창고로 선물 $w$톤을 옮기는 비용은 $|x_i - x_j| \times w$이다.

산타 코퍼레이션은 지출을 최소로 줄이려 한다. 운반 비용의 합이 가장 작아지도록 창고 $k$개를 고를 때, 그 최소 비용을 구하라.

첫째 줄에 창고의 개수 $n$과 설치할 순간이동기의 개수 $k$가 주어진다. ($1 \le k < n \le 5000$)

다음 $n$개 줄에는 $i$번 창고의 위치 $x_i$와 그 창고에 들어 있는 선물의 무게 $w_i$가 주어진다. ($1 \le x_i, w_i \le 1000000$)

창고는 위치 순서대로 주어지지 않고, 같은 위치에 창고가 여러 개 있을 수 있다.

선물을 모두 선택한 창고 $k$개로 옮겼을 때의 최소 운반 비용을 출력한다.