考え方
$1 \leq K, A_{i} \leq 2\times 10^{9}$と，大きな値を取り得る．二分探索
公式解説の方法：Editorial - AtCoder Beginner Contest 216初期値が$A_{i}$のアトラクションは，最大$A_{i}$回利用できる．
利用回数の視点で考えるのをやめ，「楽しさ$x$以上のものをすべて利用するときの利用回数$f(x)$」を計算してみる．すると，
- $f(1) = \sum_{i} A_{i}$
- $f(2) = \sum_{i} (A_{i} - 1)$
- $\cdots$
- $f(x) = \sum_{i} \max(A_{i} - x, 0)$
もし，$f(x) \leq K < f(x - 1)$なる$x$がわかれば，
\begin{aligned}
& \sum_{i} \sum_{j = x}^{A_{i}} j + (K - f(x))\cdot (x - 1)
\end{aligned}
が答えになる．第1項は楽しさ$x$以上のものをすべて（$f(x)$回）利用したときの満足度であり，第2項は第1項で消費しきれなかった分の寄与である．& \sum_{i} \sum_{j = x}^{A_{i}} j + (K - f(x))\cdot (x - 1)
\end{aligned}
この$x$は二分探索で求められる．
【参考】Submission #25423511 - AtCoder Beginner Contest 216
貪欲法
ユーザ解説の方法：Amusement Park [AtCoder Beginner Contest 216 E] - はまやんはまやんはまやん$\{A_{i}\}_{i}$を降順にソートして順に見ていく．
①$A_{0}$を$A_{1}$になるまでとっていき，
②$A_{0}, A_{1}$を$A_{2}$になるまでとっていき，
③$A_{0}, A_{1}, A_{2}$を$A_{3}$になるまでとっていき，・・・
とすればよい．
この計算では，考えているアトラクションの個数（①なら1コ，②なら2コ，．．．）とどこまでとってよいか（$A_{i} - A_{i+1}$）が必要になる．
何も考えずに上の操作ができるのは，
\begin{aligned}
& (\text{取る総数}) \leq (\text{残りの回数})
\end{aligned}
の場合である．ここで，& (\text{取る総数}) \leq (\text{残りの回数})
\end{aligned}
\begin{aligned}
& (\text{取る総数}) \\
&=(\text{考えているアトラクションの個数}) \\
&\quad
\times (\text{アトラクション1つにつき取る個数}) \\
&=(i + 1) \cdot (A_{i} - A_{i+1})
\end{aligned}
である．& (\text{取る総数}) \\
&=(\text{考えているアトラクションの個数}) \\
&\quad
\times (\text{アトラクション1つにつき取る個数}) \\
&=(i + 1) \cdot (A_{i} - A_{i+1})
\end{aligned}
この条件を満たさなくなったら，
\begin{aligned}
& (\text{アトラクション1つにつき取る個数}) \\
& = (\text{残りの回数}) /\!/ (\text{考えているアトラクションの個数})
\end{aligned}
とすればもう一度同じ操作ができる．& (\text{アトラクション1つにつき取る個数}) \\
& = (\text{残りの回数}) /\!/ (\text{考えているアトラクションの個数})
\end{aligned}
この操作のあと，$A_{i} - (\text{アトラクション1つにつき取る個数})$ の「楽しさ」のアトラクションが残りの回数より多く存在する．よって，これを残りの回数分加えれば良い．
