\(M-1\) 日後に働くアルバイトから逆順に働くアルバイトを決めていく.

\(M-1\) 日後に働いて \(M\) 日後までに報酬が得られるアルバイト, すなわち \(A_i \leq 1\) のアルバイトのうち最も報酬の高いアルバイトを選ぶ.

次に \(A_i \leq 2\) のアルバイトのうち最も報酬の高いアルバイトを選ぶ. これを順に繰り返していく.

アルバイトの管理には優先順位付きキューを使えば最も高いアルバイトを高速に取得することができる.