20637번 - The Spellbook 다국어

You have a spellbook with $n$ spells. The spells are numbered by sequential integers from $1$ to $n$, and the spell $i$ ($1 \le i \le n$) initially costs $A_i$ MP (mana points). Initially you have $m$ MP.

Your goal is to cast each spell from the spellbook exactly once.

Before you start casting spells, you can eat up to $k$ cookies. Eating a cookie takes zero time. Each time you eat a cookie, you can choose a spell with a positive cost and reduce that cost by $1$.

After eating cookies, you start casting spells.

You can repeatedly choose and perform one of the following actions:

• Choose an integer $i$ ($1 \le i \le n$) and cast the spell $i$. However, the current MP must be greater than or equal to $A_i$. This action takes zero time and decreases your MP by $A_i$.
• If your MP is $z < m$, you may take a rest to restore $1$ MP. It takes $m - z$ seconds (for example, if $m = 5$ and $z = 2$, you need to rest for $3$ seconds to regenerate MP from $2$ to $3$).

Find the minimum amount of time you can spend to cast each of the $n$ spells exactly once. You are free to select the order of the spells.

First line of the input contains three integers $n$, $m$ and $k$: the number of spells, the initial MP value and the number of cookies, respectively. The second line contains $n$ integers $A_i$: the initial costs of the spells in MP ($1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le A_i \le m$, $0 \le k \le \sum\limits_{i=1}^n A_i$).

Print one integer: the minimum amount of time it takes to cast each of the $n$ spells exactly once.