#D0170. 吃桃子

吃桃子

题目描述

33DAI 梦到自己变成了孙悟空,来到了蟠桃园,蟠桃园里一共还有 nn 个桃子。

初始 33DAI 只能吃得下一个桃子。

每个桃子有两个属性,第 ii 个桃子的属性为:aia_ibib_i。分别表示吃掉这个桃子后,33DAI 的开心程度会增加 aia_i,并且由于开胃效果很好,能让 33DAI 多吃下 bib_i 个桃子。

请问 33DAI 的开心程度最高能到多少。

输入格式

第一行为一个正整数 nn

接下来 nn 行,每行为两个正整数,第 ii 行为 ai,bia_i,b_i

输出格式

输出 33DAI 的开心程度的最大值。

5
3 0
2 0
5 0
1 0
4 0
5
5
3 0
2 0
5 0
1 1
4 2
13

样例解释

  • 样例 1 中,33DAI 只能选择吃掉 (5,0)(5,0) 那个桃子。
  • 样例 2 中,33DAI 可以按照 (1,1),(4,2),(3,0),(5,0)(1,1),(4,2),(3,0),(5,0) 的顺序吃掉四个桃子。

数据规模与约定

对于 100%100\% 的数据,1n10001 \le n \le 10000ai,bi1000\le a_i,b_i\le 100

  • 子任务 1(30 分):bi=0b_i=0
  • 子任务 2(30 分):ai=1a_i=1
  • 子任务 3(40 分):没有特殊限制。