[GDKOI2024 DAY1 普及组] 刷野 III

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第一试

2024 年 1 月 6 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。

但是由于某种神秘原因，Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$，Zayin 每次攻击第 $i$ 只怪物时，实际上是在攻击第 $p_i$ 只怪物。

Zayin 每次可以选择一个 $[1, n]$ 的整数 $k$，让第 $p_k$ 只怪物的血量减少 $1$ 点，当某只怪物的血量小于等于 $0$ 时这只怪物死亡。

然而 Zayin 并不知道这个排列 $p$ 具体是什么，也无法看到每个怪物剩余的具体血量，仅可以知道每次攻击完后怪物是否死亡。

现在 Zayin 想知道，在他采取最优策略的情况下，最多需要攻击多少次，才可以杀死 $m$ 只怪物。

输入格式

输入的第一行包含两个正整数 $n, m(1 \leq m \leq n \leq 2000)$，$n$ 表示怪物的个数，$m$ 表示 Zayin 所需要击杀的怪物个数。

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^9)$，$a_i$ 表示第 $i$ 只怪物的血量。

输出格式

输出一个整数，最少的攻击次数。

样例 #1

样例输入 #1

2 1
10 15

样例输出 #1

15

样例 #2

样例输入 #2

2 1
10 30

样例输出 #2

20

提示

【样例解释】

在第一个样例，Zayin 会一直攻击某一只怪物，直到怪物死亡。

在第二个样例，Zayin 先攻击某一个怪物 $10$ 次，如果没有死亡，则说明攻击的是 $30$ 血的怪物。这时 Zayin 会选择攻击第二只怪物，攻击 $10$ 次后另一只怪物一定死亡，故最差需要 $20$ 次。

【数据范围】

对于 $10\%$ 的数据，$1 \leq n, m \leq 5$。

对于另外 $20\%$ 的数据，所有 $a_i$ 全部相等。

对于另外 $30\%$ 的数据，$1 \leq m \leq n \leq 500$。

对于 $100\%$ 的数据，$1 \leq m \leq n \leq 2000$，$1 \leq a_i \leq 10^9$。