这天，小明在搬砖。

他一共有 n 块砖，他发现第 i 砖的重量为 w_i，价值为 v_i。他突然想从这些砖中选一些出来从下到上堆成一座塔，并且对于塔中的每一块砖来说，它上面所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。

输入共 n + 1 行，第一行为一个正整数 n，表示砖块的数量。

后面 n 行，每行两个正整数 w_i , v_i 分别表示每块砖的重量和价值。

5
4 4
1 1
5 2
5 5
4 3

10

选择第 1、2、4 块砖，从上到下按照 2、1、4 的顺序堆成一座塔，总价值为 4 + 1 + 5 = 10 。

对于 20% 的数据，保证 n ≤ 10；

对于 100% 的数据，保证 n ≤ 1000; w_i ≤ 20; v_i ≤ 20000 。