描述
安博士给了小明N块积木,第i个积木的重量是Wi,支撑度是Vi,安博士让小明用将这些积木一块一块叠加搭建成一个高塔。为了保证高塔的稳定,对于塔中任意一块积木X来说,搭建在X上面的所有积木的重量之和不能超过X的支撑度V。
现在安博士要求小明告诉他这个高塔的支撑度之和最大是多少?
输入
输入第1行1个整数N,表示积木的个数。
接下来输入N行,每行两个整数Wi和Vi。
输出
输出一个整数表示答案。
输入样例 1
5
4 4
1 1
5 2
5 5
4 3
输出样例 1
10
输入样例 2
10
17 15
2 48
17 11
11 28
10 49
19 3
19 23
3 36
19 23
17 1
输出样例 2
184
提示
1<=N<=1000;
1<=Wi<=20;
1<=Vi<=20000;