タスクと締め切り
複数のタスクが与えられ、それぞれ「締め切り」と「締め切りまでに完了した場合に得られる利益」が設定されています。各タスクを完了するには1日かかり、締め切りを過ぎてしまうとそのタスクの利益は得られません。
作業は1日目から始まるものとします。最終的に得られる合計利益を最大にするには、どのようにタスクをこなせばいいでしょうか？ そのときの最大合計利益はいくらになるでしょうか？
入力
最初の行に、タスクの数を示す整数
n (1 ≤ n ≤ ) が与えられます。続く
n 行には、それぞれのタスクについて空白区切りの整数 (1 ≤ , ≤ ) が記載されます。ここで はタスクの締め切りを、 はそのタスクを期日内に完了した場合の利益を表します。出力
得られる最大の合計利益を出力してください。
Examples
Input | Output |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Explanation
- 10 + 3 + 7
- まず、締め切りが1のタスクを行って3の利益を得る
- 次に、締め切りが2のタスクを行って7の利益を得る
- 最後に、締め切りが4のタスクを行って10の利益を得る
- 100 + 200 + 300 + 200（締め切りが4のタスクのみを実行）
- はじめに利益100のタスクをこなす
- 次に利益200のタスクをこなす
- 続けて利益300のタスクをこなす
- 最後に利益200のタスクをこなす
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB