2872 - 实验

题目描述

在一个科学实验室里,有 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
说明

样例 1 解释

一共有 3 个实验样本,最多有进行 4 次实验的时间。

可以按照如下顺序实验:

1 次对第 3 个样本进行实验,获得 201 分奖励。

2 次对第 3 个样本进行实验,获得 200 分奖励。

3 次对第 1 个样本进行实验,获得 200 分奖励。

4 次对第 1 个样本进行实验,获得 199 分奖励。

总分为 201+200+200+199 = 800

数据范围

对于 50\% 的数据,满足 1 \le n \le 1001 \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

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题