{"code":"19dhbbmining","name":"Mining","description":"Ở đấ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:\r\n - 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)$.\r\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.\r\n - 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$.\r\n\r\n**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.\r\n\r\n#### Input\r\n - Dòng 1 ghi hai số $N, K$.\r\n - $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$.\r\n\r\n#### Output\r\n - In giá trị bé nhất để hợp nhất số vàng về $K$ đống.\r\n\r\n#### Scoring\r\n - $1 ≤ K ≤ N ≤ 5000, 0 ≤ X_i, W_i ≤ 10^6$.\r\n - $W_i < W_{i+1}$\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    \r\n    ???+ \"Input\"\r\n    \r\n        ```sample\r\n        3 1\r\n        20 1\r\n        30 1\r\n        40 1\r\n\r\n\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        20\r\n        ```\r\n!!! question \"Test 2\"\r\n    \r\n    ???+ \"Input\"\r\n    \r\n        ```sample\r\n        6 2\r\n        10 15\r\n        12 17\r\n        16 18\r\n        18 13\r\n        30 10\r\n        32 1\r\n\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        182\r\n        ```\r\n    ??? warning \"Note\"","points":1800.0,"partial":true,"time_limit":2.5,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}