시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

2 4 0
2 4

예제 출력 1

3

예제 입력 2

3 9 6
2 3 9

예제 출력 2

0

예제 입력 3

3 16 2
6 9 9

예제 출력 3

21

예제 입력 4

2 1000000 0
1000000 1000000

예제 출력 4

500000500000