问题描述

JOI 市有一条足够长的道路。这条道路可以看作数轴，每个地点由一个实数坐标表示。此外，在JOI市沿着这条道路设置了N个设施，并为它们编号，编号从1到N，按照坐标从小到大的顺序进行编号。设施i（1≤i≤N）的位置由坐标Ai表示。

在JOI市，即将进行设施的安全检查。设施i必须检查Bi个项目。现在，已经聚集了K名工人可以进行检查。在安全检查开始时，每个工人都位于坐标0处。检查开始后，每个工人可以在1分钟内选择以下两种行动之一：

• 移动距离1。
• 在当前坐标上选择一个设施的一个检查项目进行检查。

完成安全检查时，所有建筑物的所有检查项目必须由至少一个工人进行检查。

给定工人数量和设施信息，请编写一个程序来计算完成安全检查所需的最短时间。

约束条件

• 1≤N≤100,000。
• 1≤K≤10^9。
• 1≤Ai≤10^9（1≤i≤N）。
• Ai<Ai+1（1≤i≤N-1）。
• 1≤Bi≤10^9（1≤i≤N）。
• 输入的值都是整数。

子任务

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

---

输入

从标准输入读入输入数据。输入格式如下：

N K A1 A2 … AN B1 B2 … BN

输出

将计算出的完成安全检查所需的最短时间输出到标准输出。

---

输入示例 1

3 3
1 3 4
4 2 4

输出示例 1

7

例如，通过以下行动，可以在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。

---

输入示例 2

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

输出示例 2

63

该输入示例满足子任务1和3的约束条件。

---

输入示例 3

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

输出示例 3

35

该输入示例满足子任务2和3的约束条件。

---

输入示例 4

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

输出示例 4

19