[GDKOI2024 DAY1 普及组] 刷野 I

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第一试

2024 年 1 月 6 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。

Zayin 率先使用一种攻击方式攻击，攻击过后所有血量小于等于 $0$ 的怪物死亡。在 Zayin 攻击一次后，所有存活的怪物对 Zayin 造成 $1$ 点伤害。以上步骤不断循环，直到 Zayin 击杀所有怪物为止。

Zayin 一共有三种攻击方式：

• 普通攻击: 消耗 $0$ 点能量值，选择一只怪物并使其血量减少一点。
• 天音波: 消耗 $1$ 点能量值，选择一只怪物并使其血量减少两点。
• 天雷破: 消耗 $1$ 点能量值，使所有怪物血量减少一点。

现在 Zayin 一共有 $m$ 点能量，现在他想知道在最优的策略下，击败 $n$ 只怪物所损失的最少血量。

输入格式

输入的第一行包含两个正整数 $n, m(1 \leq n, m \leq 10^5)$，$n$ 表示怪物的个数，$m$ 表示 Zayin 拥有的能量值。

输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^9)$，$a_i$ 表示第 $i$ 只怪物的血量。

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

3 4
2 4 4

样例输出 #1

6

提示

对于 $30\%$ 的数据，$1 \leq n, m \leq 5$。

对于另外 $15\%$ 的数据，$m = 0$。

对于另外 $15\%$ 的数据，所有 $a_i$ 全部相等。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$，$1 \leq a_i \leq 10^9$。