题目描述

今天是 YQH 的生日，她得到了一个记载了 $n$ 条魔咒的魔法书和 $k$ 个魔法饼干作为礼物，其中第 $i$ 条魔咒需要花费 $a_i$ 点蓝。作为一名见习魔法师，YQH 初始拥有 $m$ 点蓝。

YQH 是一个充满好奇心的女孩子，她在得到魔法书的那一刻就想要把魔法书里的每一条魔咒都至少使用一次。但是她自己的蓝太少了，而补蓝需要花钱。具体的，YQH 可以做下列三种操作：

• 选择一条未使用过的魔咒，假设选择的魔咒是第 $i$ 条。如果 YQH 持有的蓝大于等于 $a_i$ 点，那么她持有的蓝减去 $a_i$ 点，并记录第 $i$ 条魔咒为使用过。
• 如果还有魔法饼干，YQH 可以吃掉一个魔法饼干并选择一条魔咒，假设选择的魔咒是第 $i$ 条。如果此时 $a_i\ge 1$，那么令 $a_i$ 减一。
• 假如现在 YQH 持有 $a$ 点蓝，且 $a < m$，那么 YQH 可以花费 $m-a$ 块钱来使自己持有的蓝加一。也就是说，假如 $m=4,a=1$，那么 YQH 把蓝补满的花费为 $3+2+1=6$。

聪明的你一定知道 YQH 把每条魔咒都使用过一遍所需最少的钱了，请把这个数目告诉她吧。注意，你不需要最小化饼干的使用数，也不需要关心最后 YQH 持有多少蓝。

输入格式

第一行三个正整数 $n,m,k$。分别表示魔咒数量，YQH 初始蓝数，魔法饼干数量

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示魔咒的花费。

输出格式

第一行一个整数表示 YQH 把每条魔咒都使用一遍所需最少钱数。

样例

输入1

2 4 0
2 4

输出1

3

其中一种最优操作为：YQH 先使用第一条魔咒，此时 YQH 持有 $2$ 点蓝，之后 YQH 补两次魔，花费 $2+1=3$ 块钱，最后 YQH 使用第二条魔咒，总花费钱数为 $3$。

输入2

3 16 2
6 9 9

输出2

21

YQH 先吃两个饼干，使 $a_2,a_3$ 都变成 $8$，然后使用第一条魔咒，此时 YQH 持有 $10$ 点蓝，然后 YQH 补六次魔，花费 $6+5+4+3+2+1=21$ 块钱，最后 YQH 依次使用第二、三条魔咒。

输入3

3 9 1
2 3 9

输出3

6

YQH 吃一个饼干，使 $a_2$ 变为 $2$，然后使用第一条魔咒，补两次魔，花费 $2+1=3$ 块钱，使用第二条魔咒，补两次魔，花费 $2+1=3$ 块钱，最后使用第三条魔咒。总花费为 $6$，可以证明没有更优的方案。

样例输入/输出 4

见下发文件中的 ex_biscuit4.in/ex_biscuit4.ans。

数据范围

对于所有数据，保证 $1\le n\le 10^5,1\le m\le 10^6,1\le a_i\le m,0\le k\le \sum a_i$。