Let \(\mathrm{dp}_{i,j}\) (DP stands for Dynamic Programming) be the maximum \(X-Y\) (for Takahashi’s turn) or \(Y-X\) (for Aoki’s turn) starting from the state where \(j\) bags remain, whose leftmost bag was the \(j\)-th bag from the left in the original state. Then, the transition of paying \(Z\) yen to take bags so that \(k\) bags remain is

• \(\mathrm{dp}_{i,j} = \max_{j \leq l \leq i+j-k} (S(i,j) - S(k,l) - \mathrm{dp}_{k,l} - Z)\),

where \(S(a,b)\) is the total amount of money in the \(b\)-th, \((b+1)\)-th, \(\ldots\), and \((b+a-1)\)-th bag from the left in the original state.

If you naively implement this, it will cost \(\mathrm{O}(N^3)\) time; however, you can transform it as follows so that you can use a segment tree or the sliding-window minimum trick to solve it in a total of \(\mathrm{O}(N^2 \log N)\) or \(\mathrm{O}(N^2)\) time.

• \(\mathrm{dp}_{i,j} = S(i,j) - Z - \min_{j \leq l \leq i+j-k}( S(k,l) +\mathrm{dp}_{k,l} )\)