← 返回题目列表

AtCoder · joi2018ho_a

A. 炉子

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

配点: 100 点

JOI 你的房间里有一个炉子。 JOI 当你独自一人在房间里时,你不需要打开炉子,因为你耐寒,但当你有客人来访时,你确实需要打开炉子。

这一天,JOI与你同在 N 有访客。i 番目 (1 \leqq i \leqq N) 访客到达时间 到达 T_i 和时间 退出至 T_i + 1 。同一时间不会有超过一名访客。

JOI 您可以随时打开和关闭炉灶。但是,每次打开炉子时,都要使用火柴。 1 阅读这本书。 JOI你匹配 K 我只有书,所以 您最多只能打开炉灶K 次。一天一开始,炉子就关掉了。

炉子打开时,燃料会相应消耗,因此最好设置炉子打开和关闭的时间,以尽量减少炉子打开的总时间。

課題

JOI 根据您房间的访客信息和您拥有的火柴数量,找出炉子打开的最短总时间。


入力

从标准输入读取以下输入。

  • 1 行表示,2 整数 N, K 以空格作为分隔符。这是在你房间里的 JOI N 有访客,JOI君。 K 表示您有图书匹配。
  • 继续 N 行中的 i 行目 (1 \leqq i \leqq N) 是一个整数 写入 T_i 。这是i 第 位访客 时间到了 T_i 和时间 退出至 T_i + 1 代表退出。

出力

设置炉子打开到标准输出的总时间的最小值。 1 行上。


制限

所有输入数据满足以下条件。

  • 1 \leqq N \leqq 100\,000.
  • 1 \leqq K \leqq N.
  • 1 \leqq T_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • T_i < T_{i+1} (1 \leqq i \leqq N - 1).

小課題

小課題 1 [20 点]

满足以下条件。

  • N \leqq 20.
  • 1 \leqq T_i \leqq 20 (1 \leqq i \leqq N).

小課題 2 [30 点]

  • N \leqq 5\,000 很满意。

小課題 3 [50 点]

  • 没有其他限制。

入力例 1

3 2
1
3
6

出力例 1

4

在此输入示例中,JOI 房间的访客是 3 有人。如果您如下图所示打开和关闭炉灶,则有客人时炉灶将保持打开状态,并且打开炉灶的次数将受到限制。 2 次,炉子打开的总时间是 (4 - 1) + (7 - 6) = 4 。

  • 1 第位访客到达时间 将炉子连接到 1 。
  • 2 第位访客离开的时间 在 4 处关闭炉子。
  • 3 第位访客到达时间 将炉子连接到 6 。
  • 3 第位访客离开的时间 在 7 处关闭炉子。

计算炉子打开的总时间。 它不能小于 4 ,所以答案是 4 。


入力例 2

3 1
1
2
6

出力例 2

6

在此输入示例中,JOI 是 1 我只能打开炉子一次,所以1 第位访客到达时间 将炉子连接到 1 打开炉子, 只需在3 第位访客离开的时间 在 7 处关闭炉子即可。

请注意,访客离开的时间可能与下一位访客到达的时间一致。


入力例 3

3 3
1
3
6

出力例 3

3

在此输入示例中,JOI 可以在每次客人到达时打开炉灶,并在每次客人离开时关闭炉灶。


入力例 4

10 5
1
2
5
6
8
11
13
15
16
20

出力例 4

12