Di cư

Trên hành tinh Zeta, một cơn bão plasma khổng lồ đang chuẩn bị quét qua một vùng dân cư đông đúc. Để ứng phó, chính quyền hành tinh đã điều động các phi thuyền cứu hộ tại nhiều trạm không gian khác nhau nhằm sơ tán dân cư đến nơi an toàn.

Hiện tại có N trạm không gian, trạm thứ \(i\) chứa \(w_i\) người và tọa lạc tại vị trí \(x_i\) trên một trục không gian một chiều. Tuy nhiên, do thiếu hụt năng lượng, chỉ có đúng \(K\) phi thuyền có thể khởi động và đóng vai trò điểm tập kết. Mỗi phi thuyền phải đặt trên một trạm không gian trong \(N\) trạm đã cho.

Các trạm không gian khác sẽ phải di chuyển người dân đến một trong những trạm được chọn. Chi phí để di chuyển toàn bộ \(w_i\) người tại trạm \(i\) đến trạm \(j\) là \(w_i \cdot |x_i - x_j|\).

Yêu cầu: Chọn ra đúng \(K\) trạm đóng vai trò trạm tập kết hoạt động, rồi phân công người dân từ các trạm còn lại đến một trạm tập kết sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) \((1 \leq K \leq N \leq 5000)\) --- số lượng trạm và số lượng trạm tập kết hoạt động.
• \(N\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(x_i\), \(w_i\) \((1 \leq x_i, w_i \leq 10^6)\) --- vị trí và số người tại trạm thứ \(i\).

Output

• Ghi ra một số nguyên --- chi phí nhỏ nhất để di chuyển toàn bộ người dân tới các trạm tập kết được chọn.

Example

3 1
20 1
30 1
40 1

20

3 1
11 3
12 2
13 1

4

6 2
10 15
12 17
16 18
18 13
30 10
32 1

182

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số test có \(N \leq 20\).

• Có \(30\%\) số test tương ứng với \(30\%\) số test có \(N \leq 100\).

• Có \(30\%\) số test tương ứng với \(30\%\) số test có \(N \leq 500\).

• Có \(20\%\) số test tương ứng với \(20\%\) số test còn lại không có ràng buộc gì thêm.