分数: 400 分
问题陈述
Takahashi 在配送中心工作,必须将包裹从仓库配送至 N 目的地。
仓库和所有目的地都位于一条数轴上。仓库位于坐标 0,以及 i- 第一个目的地位于坐标处 X_i (X_i 可以是正数或负数)。所有目的地坐标都彼此不同,也与仓库位置不同(坐标 0)。正是如此 D_i 包裹必须递送至 i- 第一个目的地。仓库最初拥有所有目的地的所有包裹,总计 \sum_{i=1}^{N} D_i 包。
高桥使用的推车有容量限制,最多可以承载 K 一次打包。高桥重复以下过程,直到将所需数量的包裹递送到所有目的地:
- 加载包: 在仓库(坐标 0),从以下位置加载任意数量的包 1 to K 到购物车上。但是,他装载的数量不能超过所有目的地未投递包裹的剩余总数。
- 交付: 离开仓库并沿着数轴自由移动,将任意数量的包裹从购物车运送到任何目的地。一次配送行程可以到达多个目的地,一次行程可以到达正反两个方向的目的地。例如,可以先朝正方向运送到某些目的地,然后再折回负方向运送到目的地。投递至每个目的地的包裹数量不得超过该目的地剩余的未投递数量。无需交付购物车上装载的所有包裹;未交付的包裹被带回仓库并可用于后续交付。 注意,即使他经过仓库(坐标 0) 在送货行程中,他无法装载额外的包裹。
- 退回仓库: 返回仓库(坐标 0).
到每个目的地的送货可以分多次进行。例如,如果 5 包裹需要投递到目的地,可以投递 3 一趟并且 2 在另一个。
单次配送行程的行驶距离是高桥从出仓到返回仓库实际行驶的总距离。距坐标移动的距离 a 协调 b is |a - b|。例如,如果他从仓库(坐标 0) 来协调 5,返回坐标 -3,返回仓库(坐标 0),行驶距离为 5 + 8 + 3 = 16.
Takahashi 希望最大程度地减少所有配送行程的总行程距离,直到所有包裹送达并且他已返回仓库(坐标 0).
求最小总行驶距离。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- -10^9 \leq X_i \leq 10^9
- X_i \neq 0
- 全部 X_i 是不同的
- 1 \leq D_i \leq 10^9
- \sum_{i=1}^{N} D_i \leq 10^9
- 所有输入均为整数
输入
N K X_1 D_1 X_2 D_2 \vdots X_N D_N
第一行包含目的地数量 N 和最大包裹数 K 可以一次加载到购物车上,中间用空格分隔。的 i- 以下各项 N 行包含坐标 X_i 的 i- 第一个目的地和包裹数量 D_i 需要传送到那里,并用空格分隔。
输出
在一行中打印出所有包裹送达且 Takahashi 返回仓库之前的最小总行程距离(坐标 0).
示例输入 1
3 3 2 2 -4 1 5 2
示例输出 1
22
示例输入 2
2 2 -3 3 -1 1
示例输出 2
12
示例输入 3
8 5 -10 4 7 3 -2 6 15 2 4 5 -6 1 12 7 -14 3
示例输出 3
128
示例输入 4
20 7 -100 8 35 3 -12 15 80 6 5 9 -55 4 120 11 -3 2 60 7 -200 5 18 13 -75 10 150 1 -30 6 95 14 -140 3 42 8 -8 12 210 4 -180 9
示例输出 4
3366
示例输入 5
1 1000000000 -1000000000 1000000000
示例输出 5
2000000000