题目描述

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$ 只怪物的血量。

输出格式

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

2 1
10 15

15

2 1
10 30

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$。