H: 魔法使いの塔

問題文

あなたが持っている魔導書には、 $N$ 個の魔法が載っています。

魔法には $1$ から $N$ までの番号がついていて、魔法 $i (1 \le i \le N)$ のコストははじめ整数 $A_i$ です。

あなたの目的は、魔導書に載っているすべての魔法を $1$ 回ずつ唱えることです。

魔法を唱えはじめる前に、あなたはクッキーを $K$ 枚食べることができます。クッキーを食べるのに時間はかかりません。

あなたはクッキーを $1$ 枚食べるたびに、コストが正の魔法を $1$ つ選び、そのコストを $1$ 下げることができます。

クッキーを食べたあと、あなたは魔法を唱え始めます。

あなたの MP ははじめ $M$ です。あなたは以下のどちらかを繰り返して、 $N$ 個の魔法を任意の順番で $1$ 回ずつ唱えます。

• 整数 $i (1 \le i \le N)$ を $1$ つ選び、魔法 $i$ を唱える。ただし、 現在の MP は魔法 $i$ のコスト以上でなければならない。
  • 時間は経過しない。
  • MP を魔法 $i$ のコストだけ消費する。
• 休憩する。ただし、現在の MP を $m$ とすると、 $m < M$ でなければならない。
  • 時間が $M - m$ 経過する。
  • MP を $1$ 回復する。

あなたが $N$ 個の魔法を任意の順番で $1$ 回ずつ唱えるためにかかる時間の最小値を求めてください。

制約

• $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$
• 入力はすべて整数である。

入力例1

2 4 0
2 4

出力例1

3

どの魔法のコストも減らすことができないので、このまま魔法を唱えていくことにします。

• まず、魔法 $1$ を唱えます。 MP を $2$ 消費するので、残りの MP は $4 - 2 = 2$ になります。

魔法 $2$ を唱えるには MP が $4$ 必要なので、このままでは魔法 $2$ を唱えることはできません。

• 休憩します。時間が $4 - 2 = 2$ 秒経過します。 MP を $1$ 回復するので、残りの MP は $2 + 1 = 3$ になります。
• 休憩します。時間が $4 - 3 = 1$ 秒経過します。 MP を $1$ 回復するので、残りの MP は $3 + 1 = 4$ になります。
• 魔法 $2$ を唱えます。 MP を $4$ 消費するので、残りの MP は $4 - 4 = 0$ になります。

以上より、時間を $2 + 1 = 3$ 秒かければ、魔法 $1,2$ を $1$ 回ずつ唱えることができます。 これより短い時間ですべての魔法を唱えることはできないので、求める答えは $3$ となります。

入力例2

3 9 6
2 3 9

出力例2

0

最終的な魔法のコストを $2, 2, 4$ とすると、休憩することなくすべての魔法を唱えることができます。

入力例3

3 16 2
6 9 9

出力例3

21

入力例4

2 1000000 0
1000000 1000000

出力例4

500000500000

答えは 32bit 整数で表せる範囲に収まらないことがあります。