\(f(x)\) を，「 \(x\) 本の空き瓶を所持している状態から飲むことのできるコーラの本数の最大値」と定義します．この問題の答えは \(f(N) + N\) と表されるので， \(f(N)\) を求めることを考えます．

最初に取る行動について考えることで，以下の漸化式が成り立つことがわかります:

\[ \begin{aligned} f(0) &= 0, \\ f(x) &= \max_{A_i \leq x} f(x-A_i + B_i) + B_i \quad (x > 0). \end{aligned} \]

補足: 下式で， \(A_i \leq x\) を満たす \(i\) が存在しない場合 \(f(x)\) を定義できませんが， \((A_i,B_i) = (1, 0)\) に対応する行動（つまり，持っている空き瓶 1 本を手放す行動）を許すことで解決されます．

\(K \coloneqq \max A\) とします． \(x < K\) に対しては，漸化式に従って \(f(x)\) を愚直に計算することができます． 公式解説 で説明されているように， \(A_i\) が等しい \(i\) について， \(B_i\) が最大となるもの以外を無視しても良いので， \(f(0), f(1), \dots, f(K-1)\) を \(O(M + K^2)\) 時間で計算できます．

\(x \geq K\) ならば，条件 \(A_i \leq x\) はどの \(i\) についても成り立ちます．ここで， \(C_y \quad (y = 1,2,\dots,K)\) を， \(A_i - B_i = y\) を満たす \(i\) における \(B_i\) の最大値と定義します．ただし，そのような \(i\) が存在しない場合は \(C_y= 0\) とします． \(C\) を用いると，先程の漸化式は

\[ f(x) = \max_{1 \leq y \leq K} f(x-y) + C_y \quad (x \geq K) \]

と表され，これは半環 \((\mathbb{Z} \cup \{-\infty\}, \max, +)\) 上の \(K\) 階線形漸化式です．この半環の元を要素に持つ行列について，乗法に関する結合法則が成り立つので，Kitamasa 法を用いると \(O(K^2 \log N)\) 時間で \(f(N)\) を計算できます．

以上で \(O(M + K^2 \log N)\) 時間の解法が得られました．