答えで二分探索をし、\(m\) 人以上を脱出させられるか判定問題を考えることにします。 \(m\) 人以外にメダルを与えるのは無駄なので、初日が始まる前に \(m\) 人以外脱落させます。

新たに以下の操作を\(i\)日目の開始時点に行えるとしてよいです。

• \(j\) \((j<i)\) 日目に脱出した園児を再合流 する。\(C_j-(B_{j+1}+B_{j+2}+\dots+B_{i-1})\ge 0\) の場合、この枚数のメダルを得てこの園児を脱出していないことにする。

ここで, \(S_{i}=\sum_{j=1}^{i}B_{j}\) とすると、再合流 で得られるメダルは \(C_{j}+S_{j}-S_{i-1}\) と書けます。

すると、各日について以下の事を行えばよいです。

• 脱出済みの園児で、再合流 してその日に再脱出しても損しない園児を全員再合流させる。
• 残りの園児に \(B_i\) 支払い切れない場合、再合流によって得られるメダルの多い園児から順に 再合流 させる。
• 現在いる園児全員に \(B_i\) 支払う。
• 現在いる園児のうち、残りのメダルで脱出できる者を全員脱出させる。

各日の脱出者について、\(C_{j}+S_{j}\) と人数のペアを優先度付きキューなどで管理することで上記の操作は実現できます。計算量は二分探索の回数と併せて \(O(N\log{N}\log{A_{1}})\) 程度です。