Wizard Tower

Problem statement

The spellbook you have contains $N$ of spells.

Magic is numbered from $1$ to $N$, and the cost of magic $i (1 \ le i \ le N)$ is initially an integer $A_i$.

Your goal is to cast all the spells in the spellbook $1$ each.

You can eat $K$ of cookies before you start casting magic. It doesn't take long to eat cookies.

For every $1$ you eat a cookie, you can choose a magic with a positive cost of $1$ and reduce that cost by $1$.

After eating the cookie, you start casting magic.

Your MP is initially $M$. You repeat either of the following to cast $N$ of magic $1$ in any order.

• Choose an integer $i (1 \ le i \ le N)$ for $1$ and cast the magical $i$. However, the current MP must cost more than the magical $i$.
• Time does not elapse.
• Consume MP for the cost of magical $i$.
• Rest. However, if the current MP is $m$, then $m <M$ must be.
• Time elapses $M --m$.
• Recover $1$ MP.

Find the minimum amount of time it will take you to cast $N$ of spells $1$ each in any order.

Constraint

• $1 \ leq N \ leq 10 ^ 5$
• $1 \ leq M \ leq 10 ^ 6$
• $0 \ leq K \ leq \ sum_ {i = 1} ^ {N} A_i$
• $1 \ leq A_i \ leq M$
• All inputs are integers.

---

input

Input is given from standard input in the following format.

$N$ $M$ $K$ $A_1$ $A_2$ $\ ldots$ $A_N$

output

Print the minimum amount of time it takes to cast $N$ of magic $1$ each.

---

Input example 1

2 4 0 twenty four

Output example 1

3

Since the cost of any magic cannot be reduced, I will continue to cast magic as it is.

• First, cast the magic $1$. It consumes $2$ of MP, so the remaining MP is $4-2 = 2$.

You cannot cast magic $2$ as it is because you need $4$ MP to cast magic $2$.

• I'll take a rest. Time elapses $4-2 = 2$ seconds. It recovers $1$ of MP, so the remaining MP is $2 + 1 = 3$.
• I'll take a rest. Time elapses $4-3 = 1$ seconds. It recovers $1$ of MP, so the remaining MP is $3 + 1 = 4$.
• Cast magic $2$. It consumes $4$ of MP, so the remaining MP is $4-4 = 0$.

From the above, if the time is $2 + 1 = 3$ seconds, the magic $1,2$ can be cast $1$ each time. You can't cast all the spells in less time, so the answer you're looking for is $3$.

---

Input example 2

3 9 6 2 3 9

Output example 2

0

With a final magic cost of $2, 2, 4$, you can cast all the magic without a break.

---

Input example 3

3 16 2 6 9 9

Output example 3

twenty one

---

Input example 4

2 1000000 0 1000000 1000000

Output example 4

500000500000

The answer may not fit in the range that can be represented by a 32-bit integer.

Example

Input

2 4 0 2 4

Output

3

inputFormat

inputs are integers.

---

input

Input is given from standard input in the following format.

$N$ $M$ $K$ $A_1$ $A_2$ $\ ldots$ $A_N$

outputFormat

output

Print the minimum amount of time it takes to cast $N$ of magic $1$ each.

---

Input example 1

2 4 0 twenty four

Output example 1

3

Since the cost of any magic cannot be reduced, I will continue to cast magic as it is.

• First, cast the magic $1$. It consumes $2$ of MP, so the remaining MP is $4-2 = 2$.

You cannot cast magic $2$ as it is because you need $4$ MP to cast magic $2$.

• I'll take a rest. Time elapses $4-2 = 2$ seconds. It recovers $1$ of MP, so the remaining MP is $2 + 1 = 3$.
• I'll take a rest. Time elapses $4-3 = 1$ seconds. It recovers $1$ of MP, so the remaining MP is $3 + 1 = 4$.
• Cast magic $2$. It consumes $4$ of MP, so the remaining MP is $4-4 = 0$.

From the above, if the time is $2 + 1 = 3$ seconds, the magic $1,2$ can be cast $1$ each time. You can't cast all the spells in less time, so the answer you're looking for is $3$.

---

Input example 2

3 9 6 2 3 9

Output example 2

0

With a final magic cost of $2, 2, 4$, you can cast all the magic without a break.

---

Input example 3

3 16 2 6 9 9

Output example 3

twenty one

---

Input example 4

2 1000000 0 1000000 1000000

Output example 4

500000500000

The answer may not fit in the range that can be represented by a 32-bit integer.

Example

Input

2 4 0 2 4

Output

3

样例

2 4 0
2 4

3