Today is YQH's birthday, and she received a magic book containing $n$ spells and $k$ magic cookies as a gift. The $i$-th spell requires $a_i$ mana to cast. As a novice mage, YQH starts with $m$ mana.

YQH is a curious girl, and the moment she received the magic book, she wanted to cast every spell in the book at least once. However, she has too little mana, and replenishing mana costs money. Specifically, YQH can perform the following three operations:

• Choose an unused spell, say the $i$-th spell. If YQH has at least $a_i$ mana, she spends $a_i$ mana and records the $i$-th spell as used.
• If she has magic cookies, YQH can eat one magic cookie and choose a spell, say the $i$-th spell. If $a_i \ge 1$, she can decrease $a_i$ by one.
• If YQH currently has $a$ mana, where $a < m$, she can spend $m-a$ money to increase her mana by one. That is, if $m=4$ and $a=1$, the cost for YQH to refill her mana is $3+2+1=6$.

As a clever person, you surely know the minimum amount of money required for YQH to cast every spell at least once. Please tell her this amount. Note that you do not need to minimize the number of cookies used, nor do you need to care about how much mana YQH has left at the end.

Input

The first line contains three positive integers $n, m, k$, representing the number of spells, YQH's initial mana, and the number of magic cookies, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the mana cost of each spell.

Output

The first line contains an integer representing the minimum cost for YQH to cast every spell at least once.

Examples

Input 1

2 4 0
2 4

Output 1

3

One optimal strategy is: YQH first casts the first spell, at which point YQH has $2$ mana. Then, YQH refills her mana twice, costing $2+1=3$ money. Finally, YQH casts the second spell. The total cost is $3$.

Input 2

3 16 2
6 9 9

Output 2

21

YQH first eats two cookies, making $a_2$ and $a_3$ both $8$. Then she casts the first spell, at which point YQH has $10$ mana. Then YQH refills her mana six times, costing $6+5+4+3+2+1=21$ money. Finally, YQH casts the second and third spells in order.

Input 3

3 9 1
2 3 9

Output 3

6

YQH eats one cookie, making $a_2$ become $2$. Then she casts the first spell, refills her mana twice (costing $2+1=3$), casts the second spell, refills her mana twice (costing $2+1=3$), and finally casts the third spell. The total cost is $6$. It can be proven that no better strategy exists.

Input 4

See ex_biscuit4.in/ex_biscuit4.ans in the provided files.

Constraints

For all data, it is guaranteed that $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$.