#3919. 魔力试卷探险

魔力试卷探险

🎲🐇🐱 兔猫信奥学院·魔力试卷探险

在兔猫信奥学院的荣耀殿堂,加菲老师为小兔和小猫精心设计了一场“魔力试卷探险”:
一排魔法试卷(编号从 00 开始)诉说着古老传说——每张试卷刻有两种符文:

  • 奖励积分 pointsipoints_i:解答可获得的分数;
  • 脑力消耗 brainpoweribrainpower_i:因过度思考,解答后必须跳过接下来的 brainpoweribrainpower_i 张试卷。

若跳过某张试卷,则可自由决定下张试卷的操作。小兔小猫需沿序列前行,合理取舍“解答”或“跳过”,以获得最高总积分


输入格式

第一行:整数 L,表示试卷总数  
接下来 L 行:每行两个整数 points_i brainpower_i
  • 1L1051 \le L \le 10^5
  • 1pointsi,brainpoweri1051 \le points_i,\,brainpower_i \le 10^5

输出格式

一个整数,表示可获得的最高总积分

4
3 2
4 3
4 4
2 5
5
  • 解释:
    • 解答试卷 0,得 33 分,跳过编号 1、2;
    • 到达试卷 3,解答得 22 分;
    • 总积分 3+2=53 + 2 = 5

5
1 1
2 2
3 3
4 4
5 5
7
  • 解释:
    • 跳过试卷 0;
    • 解答试卷 1,得 22 分,跳过 2、3;
    • 到达试卷 4,解答得 55 分;
    • 总积分 2+5=72 + 5 = 7