开始 2025-01-21 00:00:00

京师海码信奥月赛(一)

结束 2025-03-07 00:00:00
Contest is over.
当前 2025-04-19 14:44:34

D. 吃桃子

描述

海码 梦到自己变成了孙悟空,来到了蟠桃园,蟠桃园里一共还有 n 个桃子。

初始 海码 只能吃得下一个桃子。

每个桃子有两个属性,第 i 个桃子的属性为:a_ib_i。分别表示吃掉这个桃子后,33DAI 的开心程度会增加 a_i,并且由于开胃效果很好,能让 海码 多吃下 b_i 个桃子。 请问 海码 的开心程度最高能到多少。

输入

第一行为一个正整数 n

接下来 n 行,每行为两个正整数,第 i 行为 a_i,b_i

输出

输出 海码 的开心程度的最大值。

样例

输入

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 中,海码 只能选择吃掉 (5,0) 那个桃子。
  • 样例 2 中,海码 可以按照 (1,1),(4,2),(3,0),(5,0) 的顺序吃掉四个桃子。

数据规模与约定

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

  • 数据范围 1(30 分):b_i=0
  • 数据范围 2(30 分):a_i=1
  • 数据范围 3(40 分):没有特殊限制。

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交