U629374 最小等待时间 (waiting)

Gaffice的银行有 $n$ 个客户，第 $i$ 个客户在 $arrive_i$ 时刻到达，需要 $need_i$ 分钟办理业务。银行有 $k$ 个窗口，Gaffice希望安排客户到窗口，使得所有客户的总等待时间最小。 等待时间定义：对于客户 $i$，如果他在 $start_i$ 时刻开始办理业务，则等待时间为 $start_i - arrive_i$。 注意： 1. 客户按到达时间顺序排队（先到先服务） 2. 每个窗口每次只能为一个客户服务 3. 当有窗口空闲时，队列中最前面的客户会立即前往该窗口 4. 如果多个窗口同时空闲，客户会选择编号最小的窗口

第一行两个整数 $n$, $k$.分别表示客户数量和窗口数量 接下来 $n$ 行，每行两个整数 $arrive_i$, $need_i$ 数据保证按到达时间非递减顺序给出（即 $arrive_i ≤ arrive_{i+1}$）

输出一个整数，表示所有客户的总等待时间

**样例1解释：** - 客户1：0时刻到达，0时刻开始，等待0分钟 - 客户2：1时刻到达，3时刻开始（窗口被客户1占用），等待2分钟 - 客户3：2时刻到达，5时刻开始，等待3分钟 - 总等待时间 = 0 + 2 + 3 = 5 **样例2解释：** 窗口1：客户1(0-3), 客户3(3-4), 客户5(6-8) 窗口2：客户2(1-3), 客户4(4-9) 等待时间：客户1:0, 客户2:0, 客户3:1, 客户4:0, 客户5:0 总等待时间 = 1 ## 数据范围 | 数据点 | n 的范围 | k 的范围 | 到达时间范围 | 办理时间范围 | 特殊性质 | | :----- | :------------ | :----------- | :---------------- | :-------------- | :--------------- | | 1-2 | 1 ≤ n ≤ 100 | 1 ≤ k ≤ 10 | 0 ≤ arrive ≤ 100 | 1 ≤ need ≤ 10 | 所有客户同时到达 | | 3-4 | 1 ≤ n ≤ 1000 | 1 ≤ k ≤ 50 | 0 ≤ arrive ≤ 1000 | 1 ≤ need ≤ 100 | 无 | | 5-6 | 1 ≤ n ≤ 10⁴ | 1 ≤ k ≤ 100 | 0 ≤ arrive ≤ 10⁴ | 1 ≤ need ≤ 1000 | 到达时间严格递增 | | 7-8 | 1 ≤ n ≤ 10⁵ | 1 ≤ k ≤ 1000 | 0 ≤ arrive ≤ 10⁶ | 1 ≤ need ≤ 10⁴ | 无 | | 9-10 | 1 ≤ n ≤ 5×10⁵ | 1 ≤ k ≤ 5000 | 0 ≤ arrive ≤ 10⁹ | 1 ≤ need ≤ 10⁴ | 大数据 |