Ở đất nước Yên Bình có \(N\) mỏ vàng dọc theo bờ của dòng sông và mỏ vàng thứ \(i\) có thể khai thác được \(W_i\) tấn vàng. Để phục vụ khai thác vàng, người ta cần hợp nhất và phân phối lại các mỏ vàng sao cho có đúng \(K\) đống vàng để từ đó chuyển đi bằng xe tải. Có các quy tắc sau:

• có thể di chuyển vàng giữa hai mỏ vàng \(i, j\) bất kì cho nhau với điều kiện \((0 < i < j \le N)\).
• Toàn bộ lượng vàng tại mỏ \(i\) nào đó hoặc là để yên tại \(i\), hoặc phải di dời toàn bộ qua một mỏ vàng \(j\) nào khác.
• Di chuyển \(w\) tấn vàng từ vị trí \(x_i\) đến vị trí \(x_j\) mất chi phí là \(|x_i – x_j| \times w\).

Yêu cầu: Cho \(N, K\) và số lượng vàng được sản xuất tại mỗi mỏ. Tính chi phí bé nhất để hợp nhất số vàng vào \(K\) đống theo những điều kiện trên.

Input

• Dòng 1 ghi hai số \(N, K\).
• \(N\) dòng tiếp theo mỗi dòng ghi hai giá trị \(x_i\) và \(w_i\) tương ứng với vị trí và số lượng vàng khai thác được tại mỏ thứ \(i\).

Output

• In giá trị bé nhất để hợp nhất số vàng về \(K\) đống.

Scoring

• \(1 ≤ K ≤ N ≤ 5000, 0 ≤ X_i, W_i ≤ 10^6\).
• \(W_i < W_{i+1}\)

Example

3 1
20 1
30 1
40 1

20

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

182