{"problem":{"name":"[GDKOI2024 普及组] 刷野 III","description":{"content":"Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。 但是由于某种神秘原因，Zayin 并不能控制自己打到想打的怪物。具体来说, 存在一个长度为 $n$ 的排列 $p$，Zayin 每次攻击第 $i$ 只怪物时，实际上是在攻击第 $p_i$ 只怪物。 Zayin 每次可以选择一个 $[1, n]$ 的整数 $k$，让第 $p","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10074"},"statements":[{"statement_type":"Markdown","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$ 只怪物。\n\n## Input\n\n输入的第一行包含两个正整数 $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$ 只怪物的血量。\n\n## Output\n\n输出一个整数，最少的攻击次数。\n\n[samples]\n\n## Note\n\n**【样例解释】**\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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10074","tags":["2024","广东","O2优化"],"sample_group":[["2 1\n10 15","15"],["2 1\n10 30","20"]],"created_at":"2026-03-03 11:09:25"}}