Nachia 君が好きなゲームの中に、 Join Wars という対戦型デジタルカードゲームがあります。

Join Wars では、ワールドというカード置き場に置いたカードの得点を競います。
ワールドは $N$ 個あり、それぞれワールド $1$ 、ワールド $2$ 、 $\ldots$ 、ワールド $N$ と呼ぶことにします。
ワールド $i$ ($1 \leq i \leq N$) には正整数の満員 $X _ i$ が設定されています。

あなたは、現在の手札としてカード A を $A$ 枚、カード B を $B$ 枚持っています。
また、すべてのワールドにはカードが置かれておらず、得点は $0$ です。
あなたは、以下の操作を好きな順番で、好きなだけ行います。

• (A) 手札のカード A を $1$ 枚捨てる。
• (B) ワールドに置かれたカードの得点の総和が満員未満であるワールドを $1$ つ選ぶ。選んだワールドをワールド $i$ として、手札のカード B を $1$ 枚ワールド $i$ に置く。このとき移動したカードの得点は、それよりも前にワールド $i$ に置かれたカード B の枚数とそれ以前に捨てたカード A の枚数の和に $1$ を足した値となる。

ただし、一度捨てたカードやワールドに置いたカードは、手札ではないものとします。
また、操作 (B) によってワールド $i$ の得点が $X _ i$ を超えてもよいことに注意してください。

$N$ 個のワールドの得点の総和としてありうる最大値を計算してください。

• $1 \leq N \leq 3{,}000$
• $0 \leq A \leq 10^{9}$
• $0 \leq B \leq 10^{9}$
• $1 \leq X _ i \leq 10^{9}$
• 入力はすべて整数

最終的な得点の総和の最大値を一行に出力してください。