https://atcoder.jp/contests/abc137/tasks/abc137_d
後ろから貪欲法で解ける気がする。 M-1日目を考えると、 残っている仕事のうち、 Ai=1を満たす仕事で報酬Biが最大となるものを請けるとして良いことがわかる。
必要であれば受けた仕事の順番を入れ替えて、 M-1日目にする仕事は、全てのN件の日雇いバイトの中でAi=1を満たし報酬Biが最大となる仕事である、とできる。
次にM-2日目を考えると、できる仕事はAi=1,2である仕事。Ai=1,Biが最大となる仕事は最終日にやることが決まっているので、 M-1日目と同様の考察により、それを除いた仕事のうち報酬が最大となるものを働けば良い。
以下繰り返す。