在一个科学实验室里,有 n 个实验样本,第 i 个样本的研究价值是 a_i。
每次你选择进行一次实验,你将会获得该样本当前的研究价值 a_i 的分数奖励。同时,该样本的研究价值会因为实验的进行而降低,即 a_i = a_i - 1。
实验虽好,但时间有限,你现在准备进行最多 k 次实验。请问在最优策略下,你能获得的总研究奖励是多少?
第一行包含两个整数,第一个为整数 n,表示实验样本的数量。第二个为整数 k,表示你可以进行的实验次数。
第二行有 n 个整数,其中第 i 个元素 a_i 表示第 i 个实验样本的初始研究价值。
一个整数,表示在最优策略下,你能获得的总研究奖励。
3 4 200 100 201
800
3 2024 2 3 4
19
一共有 3 个实验样本,最多有进行 4 次实验的时间。
可以按照如下顺序实验:
第 1 次对第 3 个样本进行实验,获得 201 分奖励。
第 2 次对第 3 个样本进行实验,获得 200 分奖励。
第 3 次对第 1 个样本进行实验,获得 200 分奖励。
第 4 次对第 1 个样本进行实验,获得 199 分奖励。
总分为 201+200+200+199 = 800。
对于 50\% 的数据,满足 1 \le n \le 100,1 \le k \le 3000。
对于 100\% 的数据,满足 1 \leq n \leq 10^5 , 1 \leq a_i \leq 2 \times 10^9 , 1 \leq k \leq 2 \times 10^9 。