问题描述

这天，小明在搬砖。

他一共有 $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 \leq 10$;

对于 100% 的数据, 保证 $n \leq 1000 ; w_i \leq 20 ; v_i \leq 20000$。