← 返回题单
题单练习 挑战赛 普及/提高- 题
← 上一题 下一题 →

A4549 | dloonc

来源官方 / 2024
时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

Ytiroirp的房间里有一个炉子。

因为 Ytiroirp 已经习惯了寒冷，所以当他一个人在房间里时，他不需要打开炉子。

但是，有客人时，他需要打开炉子。有一天，$n$ 位客人将拜访Ytiroirp。第 $i$ 个客人 ($1 \leq i \leq n$) 将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。任何时刻至多有一个客人访问Ytiroirp。

Ytiroirp 可以随时命令 Elbisivid 去开火或关火。但是命令次数多了，Elbisivid 就会鄙视他，所以 Ytiroirp 只有 $k$ 次命令的机会。 因此他最多可以打开炉子 $k$ 次。在一天的开始，炉子是关闭的。

当炉子打开时，它需要燃料。因此，Ytiroirp控制着他何时打开或关闭炉子，他想尽量减少炉子的总运行时间。

现 $n,k$ 和每个客人的到达时间，求炉子总运行时间的最小值。

输入格式

第 $1$ 行两个整数，分别表示 $n,k$。

第 $2\sim n+1$ 行，每行一个整数，第 $i$ 行的整数表示 $T_{i-1}$。

输出格式

输出一个整数，表示答案。

输入输出样例

输入 #1
3 2
1
3
6
输出 #1
4
输入 #2
10 5
1
2
5
6
8
11
13
15
16
20
输出 #2
12
输入 #3
6 3 
1
11
114
1145
11451
114514
输出 #3
1147
C++ 编辑器
输入
输出