#6927. 试题J:搬砖

试题J:搬砖

Background

这天,小明在搬砖。

Description

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

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

Format

Input

输入共n+1行。

第一行为一个正整数n,表示砖块的数量。

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

Output

一行,一个整数表示答案。

Samples

5
4 4
1 1
5 2
5 5
4 3
10

样例说明

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

Limitation

对于20%的数据,保证n ≤10;

对于100%的数据,保证n ≤1000; wiw_i≤ 20;viv_i ≤ 20000 。