{"raw_statement":[{"iden":"statement","content":"Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。\n\n但是由于某种神秘原因，Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$，Zayin 每次攻击第 $i$ 只怪物时，实际上是在攻击第 $p_i$ 只怪物。\n\nZayin 每次可以选择一个 $[1, n]$ 的整数 $k$，让第 $p_k$ 只怪物的血量减少 $1$ 点，当某只怪物的血量小于等于 $0$ 时这只怪物死亡。\n\n然而 Zayin 并不知道这个排列 $p$ 具体是什么，也无法看到每个怪物剩余的具体血量，仅可以知道每次攻击完后怪物是否死亡。\n\n现在 Zayin 想知道，在他采取最优策略的情况下，最多需要攻击多少次，才可以杀死 $m$ 只怪物。"},{"iden":"input","content":"输入的第一行包含两个正整数 $n, m(1 \\leq m \\leq n \\leq 2000)$，$n$ 表示怪物的个数，$m$ 表示 Zayin 所需要击杀的怪物个数。\n\n输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \\dots, a_n(1 \\leq a_i \\leq 10^9)$，$a_i$ 表示第 $i$ 只怪物的血量。"},{"iden":"output","content":"输出一个整数，最少的攻击次数。"},{"iden":"note","content":"**【样例解释】**\n\n在第一个样例，Zayin 会一直攻击某一只怪物，直到怪物死亡。\n\n在第二个样例，Zayin 先攻击某一个怪物 $10$ 次，如果没有死亡，则说明攻击的是 $30$ 血的怪物。这时 Zayin 会选择攻击第二只怪物，攻击 $10$ 次后另一只怪物一定死亡，故最差需要 $20$ 次。\n\n**【数据范围】**\n\n对于 $10\\%$ 的数据，$1 \\leq n, m \\leq 5$。\n\n对于另外 $20\\%$ 的数据，所有 $a_i$ 全部相等。\n\n对于另外 $30\\%$ 的数据，$1 \\leq m \\leq n \\leq 500$。\n\n对于 $100\\%$ 的数据，$1 \\leq m \\leq n \\leq 2000$，$1 \\leq a_i \\leq 10^9$。"}],"translated_statement":null,"sample_group":[["2 1\n10 15","15"],["2 1\n10 30","20"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}