配点: 100 点
問題文
JOI城有 1 有一条足够长的路。这条路可以看作是一条数轴,每个点都是 用 1 实数坐标表示。沿着这条路还有一条路可以通往JOI City。 N 设施已安装,并按坐标降序排列。 它们的编号最大为 1 从 N 。设施 i (1 \leqq i \leqq N) 的位置是坐标 A_i 。从
JOI City 现将对其设施进行安全检查。设施 i 有必须检查的项目。 有 B_i 。现在您可以进行检查 K 一群木匠聚集在一起。安全检查伊始,全体木工 我在 0 。当检查开始时,每个木匠 在 1 分钟内,以下内容 2 您可以执行以下两项操作之一。 将坐标移动
- 距離 1 。
- 当前坐标设施的检查项目中, 选择并检查1 项目。
完成安全检查时,将对所有建筑物的所有检查项目进行检查。1 必须经过至少一名木匠的检查。
给定木匠数量和有关设施的信息,编写一个程序来找出完成安全检查所需的最短分钟数。
制約
- 1 \leqq N \leqq 100\,000.
- 1 \leqq K \leqq 10^{9}.
- 1 \leqq A_i \leqq 10^{9} (1 \leqq i \leqq N).
- A_i < A_{i+1} (1 \leqq i \leqq N-1).
- 1 \leqq B_i \leqq 10^{9} (1 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (3 点) K = 1.
- (15 点) K = 2.
- (82 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
标准输出表示完成安全检查所需的最短分钟数。 1 输出在一行。
入力例 1
3 3 1 3 4 4 2 4
出力例 1
7
例如,通过执行以下操作,7 您可以在几分钟内完成检查。然而 3 给木匠编号,并且 表示为 1,2,3 。
- 大工 1,2,3 是坐标 移至 1 。
- 大工 1,2,3 是每个设施 检查 1 检查 1 一项一项地做。 前往
- 大工 1,2 是坐标 移至 2 并前往木匠 3 是一个设施 1 检查 1 执行该项目。
- 大工 1,2 是坐标 移至 3 并前往木匠 3 是坐标 移至 2 。
- 大工 1,2 是坐标 移至 4 并前往木匠 3 是坐标 移至 3 。
- 大工 1,2 是每个设施 检查 3 检查 1 木匠 3 是一个设施 2 检查 1 执行该项目。
- 大工 1,2 是每个设施 检查 3 检查 1 木匠 3 是一个设施 2 检查 1 执行该项目。
无论你如何表现 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