かかる時間が \(P_i\) で期限が \(H_i+P_i\) のタスクみたいに言い換えると、UTPC2011のファーストアクセプタンスと同じ問題になる。（出題時は気づいてませんでしたorz）

解説の解法２として O(N log N) 解法が紹介されている。 https://www.utpc.jp/2011/

軽く説明すると、期限が短い順に採用していき期限を超えたら \(P_i\) が最大のものを削除する。 このとき、高々 \(1\) 個削除すれば期限に収められる点に注意（最低でも直近に採用したものを削除すれば収まるため）。

https://atcoder.jp/contests/cf17-final/submissions/54036601