タスクと締め切り

複数のタスクが与えられ、それぞれ「締め切り」と「締め切りまでに完了した場合に得られる利益」が設定されています。各タスクを完了するには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

  1. 10 + 3 + 7

    1. まず、締め切りが1のタスクを行って3の利益を得る

    2. 次に、締め切りが2のタスクを行って7の利益を得る

    3. 最後に、締め切りが4のタスクを行って10の利益を得る

  2. 100 + 200 + 300 + 200(締め切りが4のタスクのみを実行)

    1. はじめに利益100のタスクをこなす

    2. 次に利益200のタスクをこなす

    3. 続けて利益300のタスクをこなす

    4. 最後に利益200のタスクをこなす

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue