AT_joi2021_yo2_d.安全点検 (Safety Inspection)

在 JOI 市有一条恒长不变的道路，它可以被看作是一条数轴。数轴上的每一个点都用一个实数坐标来表示。沿这条路分布着 $N$ 个设施，这些设施按坐标从小到大依次标记为 $1$ 到 $N$。设施 $i$ 位于坐标 $A_i$。

JOI 市计划对这些设施进行安全检查。对每个设施 $i$，需要进行 $B_i$ 个独立的检查项目。目前有 $K$ 名工人参与这次检查。在开始检查时，所有工人都位于坐标 $0$。进行检查时，工人每分钟可以选择以下两种操作之一：

• 向任意方向移动 $1$ 个单位距离。
• 在当前坐标对一个检查项目进行检查。

要完成这次检查任务，所有设施的每个检查项目都必须至少由一名工人检查。

根据给定的工人数和设施的信息，请编写程序计算完成所有安全检查所需的最短时间（分钟）。

输入以如下格式提供：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$

输出一个整数，表示完成所有安全检查所需的最短时间（分钟）。

• $1 \leq N \leq 100\,000$：设施数目。
• $1 \leq K \leq 10^{9}$：工人数。
• $1 \leq A_i \leq 10^{9}$：设施 $i$ 的坐标。
• $A_i < A_{i+1}$ ($1 \leq i \leq N-1$)：设施坐标递增。
• $1 \leq B_i \leq 10^{9}$：每个设施需要检查的项目数。

子任务

1. ($3$ 分) $K = 1$。
2. ($15$ 分) $K = 2$。
3. ($82$ 分) 没有额外限制。

样例解释

例如，可以通过以下步骤在 $7$ 分钟内完成检查。三名工人分别编号为工人 $1, 2, 3$：

1. 工人 $1, 2, 3$ 移动到坐标 $1$。
2. 工人 $1, 2, 3$ 各自完成设施 $1$ 的一个检查项目。
3. 工人 $1, 2$ 移动到坐标 $2$，工人 $3$ 继续检查设施 $1$ 的一个项目。
4. 工人 $1, 2$ 移动到坐标 $3$，工人 $3$ 移动到坐标 $2$。
5. 工人 $1, 2$ 移动到坐标 $4$，工人 $3$ 移动到坐标 $3$。
6. 工人 $1, 2$ 各自完成设施 $3$ 的一个检查项目，工人 $3$ 完成设施 $2$ 的一个检查项目。
7. 工人 $1, 2$ 各自再完成设施 $3$ 的一个检查项目，工人 $3$ 再完成设施 $2$ 的一个检查项目。

任何情况下都无法在 $7$ 分钟内完成检查，因此输出 $7$。

本翻译由 AI 自动生成