Background

2024GDKOI-PJ-day1

Description

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

但是由于某种神秘原因，Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 n 的排列 p，

Zayin 每次攻击第 i 只怪物时，实际上是在攻击第 pi 只怪物。

Zayin 每次可以选择一个 [1, n] 的整数 k，让第 pk 只怪物的血量减少 1 点，当某只怪物的血量小于等于

0 时这只怪物死亡。

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

击完后怪物是否死亡。

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

Format

Input

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

的怪物个数。

输入的第二行包含 n 个非负整数 a1, a2, ..., an(1 ≤ ai ≤ 10^9)，ai 表示第 i 只怪物的血量。

Output

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

Samples

2 1
10 15

15

2 1
10 30

20

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

在第二个样例，Zayin 先攻击某一个怪物 10 次，如果没有死亡，则说明攻击的是 30 血的怪物。这时 Zayin

会选择攻击第二只怪物，攻击 10 次后另一只怪物一定死亡，故最差需要 20 次。

Limitation

对于 10% 的数据，1 ≤ n, m ≤ 5。

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

对于另外 30% 的数据，1 ≤ m ≤ n ≤ 500

对于 100% 的数据，1 ≤ m ≤ n ≤ 2000, 1 ≤ ai ≤ 10^9。