题目描述

JOI 市内有一条非常长的道路。该道路可视为一条数轴，各点的位置由一个实数坐标表示。此外，JOI 市沿该道路设置了 $N$ 个设施，按坐标从小到大顺序编号为 1 至 $N$。设施 $i$（$1 \le i \le N$）的位置坐标为 $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$

输出格式

在标准输出中，输出一行，表示完成所有安全检查所需的最短分钟数。

3 3
1 3 4
4 2 4

7

6 1
1 4 5 6 11 15
12 5 9 8 10 4

63

6 2
1 4 5 6 11 15
12 5 9 8 10 4

35

6 5
1 4 5 6 11 15
12 5 9 8 10 4

19

提示

样例 1 解释

例如，通过以下行动，可以在 7 分钟内完成检查。此处为 3 名工人编号，分别记为工人 1、2、3：

1. 工人 1、2、3 均移动至坐标 1。
2. 工人 1、2、3 各自对设施 1 的检查项目执行 1 项检查。
3. 工人 1、2 移动至坐标 2，工人 3 对设施 1 的检查项目再执行 1 项检查。
4. 工人 1、2 移动至坐标 3，工人 3 移动至坐标 2。
5. 工人 1、2 移动至坐标 4，工人 3 移动至坐标 3。
6. 工人 1、2 各自对设施 3 的检查项目执行 1 项检查，工人 3 对设施 2 的检查项目执行 1 项检查。
7. 工人 1、2 各自对设施 3 的检查项目再执行 1 项检查，工人 3 对设施 2 的检查项目再执行 1 项检查。

无论采取何种行动，都无法在 7 分钟内完成检查，因此输出 7。

数据范围

• $1 \le N \le 100\,000$。
• $1 \le K \le 10^9$。
• $1 \le A_i \le 10^9$（$1 \le i \le N$）。
• $A_i < A_{i+1}$（$1 \le i \le N-1$）。
• $1 \le B_i \le 10^9$（$1 \le i \le N$）。
• 所有输入值均为整数。

子任务

1. （3 分）$K = 1$。
2. （15 分）$K = 2$。
3. （82 分）无额外约束。

翻译由 Qwen3-235B 完成