\(k\) の昇順に、買い物の履歴…、すなわち、買い物をした店としたときの値段を管理することを考えます（考えるだけで、実装はそのとおりにはしません）。

\(k\) を \(1\) 増やした時、履歴すべての所持金に \(1\) を増やします。その後、以下のイベントが起こる可能性があります。

• ちょうど金を使い切る場所がどこかにあるとき、そこで買い物をし、その後の履歴を抹消する。

このイベントは \(k\) を \(1\) 増やした時に高々 \(1\) 回しか起こらず、\(1\) 回追加された履歴が消去されるのも \(1\) 回だけなので、追加と消去合わせて \(O(M)\) 回しか起こりません。

この事実を使って、今度は \(k\) の降順に見ていくアルゴリズムを設計します。

\(k=M\) のときに買い物の履歴を作ります。\(k\) を \(1\) 減らした時、以下のことが起こります。

• 履歴すべての所持金を \(1\) 減らす。
• 最後の買い物ができない時、その買い物を消してそこから買い物をやり直す。

買い物をやり直すパートはセグメント木の二分探索を使えば追加 \(1\) 回につき \(O(\log N)\) で、先程の事実を使えば \(O(M\log N)\) でこの問題を解くことができます。ただこれはTLEしそうです。

最後の買い物を取り消したときの状況は一意に定まりますから、このやり直すパートをメモ化します。\(1\) 度目は真面目に計算して \(2\) 回目以降は使い回すことにすると、厳密な解析はしていませんが、これで余裕を持って間に合いました。

実装例 (C++, 1357ms)