题号：NC17971
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
山坡上有一个经济作物组成的序列
序列长度为n，第i个植物成熟时间为pi,第i个植物与第i - 1 个植物距离为di
一共有k个药农，每个药农将以1的速度从位置1出发, 你可以自由安排每个药农的出发时间，当一个药农走到某个位置时， 若该植物己经成熟，那么将其收获
植物成熟后若未被收获每秒损失1的价值，求最小损失价值
第一个植物的坐标为1
输入描述:
第一行两个整数n, k
第二行到第n+1行每行两个整数pi, di
特别的，你可以认为d1没有意义
输出描述:
一个非负整数表示最小代价
示例1
输入
复制
8 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
说明
样例解释：四个药农的出发时间分别为(1, -8, -19, -34)
备注:
对于100%的数据：n ≤ 2 * 105， k ≤ 2000， pi ≤ 109， di ≤ 104
根据相对论，药农的出发时间可以为负！
必须采摘所有植物，损失不可能为负数
题目并不难