#3054. 刷野 I

刷野 I

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

Zayin 率先使用一种攻击方式攻击,攻击过后所有血量小于等于 0 的怪物死亡。在 Zayin 攻击一次后,所

有存活的怪物对 Zayin 造成 1 点伤害。以上步骤不断循环,直到 Zayin 击杀所有怪物为止。

Zayin 一共有三种攻击方式:

• 普通攻击: 消耗 0 点能量值,选择一只怪物并使其血量减少一点。

• 天音波: 消耗 1 点能量值,选择一只怪物并使其血量减少两点。

• 天雷破: 消耗 1 点能量值,使所有怪物血量减少一点。

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

Format

Input

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

输入的第二行包含 n 个非负整数 a1, a2, ..., an(1 ≤ ai ≤ 10^9 ),ai 表示第 i 只怪物的血量。

Output

一行一个整数表示答案。

Samples

3 4
2 4 4
6

Limitation

对于 30% 的数据,1 ≤ n, m ≤ 5。

对于另外 15% 的数据,m = 0。

对于另外 15% 的数据,所有 ai 全部相等。

对于 100% 的数据,1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5 , 1 ≤ ai ≤ 10^9。