← 返回题目列表

AtCoder · joi2021_yo2_d

D. 安全检查

中文机器翻译题面 查看原题

配点: 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).
  • 所有输入值都是整数。

小課題

  1. (3 点) K = 1.
  2. (15 点) K = 2.
  3. (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. 大工 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 。


入力例 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