{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan class\u003d\"lang\"\u003e\n\u003cspan class\u003d\"lang-ja\"\u003e\n\u003ch1\u003eH: 魔法使いの塔\u003c/h1\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e問題文\u003c/h3\u003e\u003cp\u003eあなたが持っている魔導書には、 $N$ 個の魔法が載っています。\u003c/p\u003e\n\u003cp\u003e魔法には $1$ から $N$ までの番号がついていて、魔法 $i (1 \\le i \\le N)$ のコストははじめ整数 $A_i$ です。\u003c/p\u003e\n\u003cp\u003eあなたの目的は、魔導書に載っているすべての魔法を $1$ 回ずつ唱えることです。\u003c/p\u003e\n\u003cp\u003e魔法を唱えはじめる前に、あなたはクッキーを $K$ 枚食べることができます。クッキーを食べるのに時間はかかりません。\u003c/p\u003e\n\u003cp\u003eあなたはクッキーを $1$ 枚食べるたびに、コストが正の魔法を $1$ つ選び、そのコストを $1$ 下げることができます。\u003c/p\u003e\n\u003cp\u003eクッキーを食べたあと、あなたは魔法を唱え始めます。\u003c/p\u003e\n\u003cp\u003eあなたの MP ははじめ $M$ です。あなたは以下のどちらかを繰り返して、 $N$ 個の魔法を任意の順番で $1$ 回ずつ唱えます。\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e整数 $i (1 \\le i \\le N)$ を $1$ つ選び、魔法 $i$ を唱える。ただし、 現在の MP は魔法 $i$ のコスト以上でなければならない。\u003cul\u003e\n\u003cli\u003e時間は経過しない。\u003c/li\u003e\n\u003cli\u003eMP を魔法 $i$ のコストだけ消費する。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003cli\u003e休憩する。ただし、現在の MP を $m$ とすると、 $m \u0026lt; M$ でなければならない。 \u003cul\u003e\n\u003cli\u003e時間が $M - m$ 経過する。\u003c/li\u003e\n\u003cli\u003eMP を $1$ 回復する。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eあなたが $N$ 個の魔法を任意の順番で $1$ 回ずつ唱えるためにかかる時間の最小値を求めてください。\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e制約\u003c/h3\u003e\u003cul\u003e\n\u003cli\u003e$1 \\leq N \\leq 10^5$\u003c/li\u003e\n\u003cli\u003e$1 \\leq M \\leq 10^6$\u003c/li\u003e\n\u003cli\u003e$0 \\leq K \\leq \\sum_{i\u003d1}^{N} A_i$\u003c/li\u003e\n\u003cli\u003e$1 \\leq A_i \\leq M$\u003c/li\u003e\n\u003cli\u003e入力はすべて整数である。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"io-style\"\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力\u003c/h3\u003e\u003cp\u003e入力は以下の形式で標準入力から与えられる。\u003c/p\u003e\n\u003cpre\u003e$N$ $M$ $K$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力\u003c/h3\u003e\u003cp\u003e$N$ 個の魔法を $1$ 回ずつ唱えるためにかかる時間の最小値を出力せよ。\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例1\u003c/h3\u003e\u003cpre\u003e2 4 0\n2 4\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例1\u003c/h3\u003e\u003cpre\u003e3\n\u003c/pre\u003e\n\n\u003cp\u003eどの魔法のコストも減らすことができないので、このまま魔法を唱えていくことにします。\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eまず、魔法 $1$ を唱えます。 MP を $2$ 消費するので、残りの MP は $4 - 2 \u003d 2$ になります。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e魔法 $2$ を唱えるには MP が $4$ 必要なので、このままでは魔法 $2$ を唱えることはできません。\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e休憩します。時間が $4 - 2 \u003d 2$ 秒経過します。 MP を $1$ 回復するので、残りの MP は $2 + 1 \u003d 3$ になります。\u003c/li\u003e\n\u003cli\u003e休憩します。時間が $4 - 3 \u003d 1$ 秒経過します。 MP を $1$ 回復するので、残りの MP は $3 + 1 \u003d 4$ になります。\u003c/li\u003e\n\u003cli\u003e魔法 $2$ を唱えます。 MP を $4$ 消費するので、残りの MP は $4 - 4 \u003d 0$ になります。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e以上より、時間を $2 + 1 \u003d 3$ 秒かければ、魔法 $1,2$ を $1$ 回ずつ唱えることができます。\nこれより短い時間ですべての魔法を唱えることはできないので、求める答えは $3$ となります。\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例2\u003c/h3\u003e\u003cpre\u003e3 9 6\n2 3 9\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例2\u003c/h3\u003e\u003cpre\u003e0\n\u003c/pre\u003e\n\n\u003cp\u003e最終的な魔法のコストを $2, 2, 4$ とすると、休憩することなくすべての魔法を唱えることができます。\u003c/p\u003e\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例3\u003c/h3\u003e\u003cpre\u003e3 16 2\n6 9 9\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例3\u003c/h3\u003e\u003cpre\u003e21\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003chr\u003e\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e入力例4\u003c/h3\u003e\u003cpre\u003e2 1000000 0\n1000000 1000000\n\u003c/pre\u003e\n\n\u003c/section\u003e\n\u003c/div\u003e\n\n\u003cdiv class\u003d\"part\"\u003e\n\u003csection\u003e\n\u003ch3\u003e出力例4\u003c/h3\u003e\u003cpre\u003e500000500000\n\u003c/pre\u003e\n\n\u003cp\u003e答えは 32bit 整数で表せる範囲に収まらないことがあります。\u003c/p\u003e\u003c/section\u003e\n\u003c/div\u003e\n\u003c/span\u003e\n\u003c/span\u003e\n"}}]}