logo AlgoBeat OnlineJudge
登录 注册

#213812. 「KFCOI Round #2」夏日·弥光

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

他清楚地知道这一次醒来,将不会看见阳光里天使低头,似乎要亲吻他的嘴唇。

原本就剩着不多的夕阳彻底坠落下去,铺天盖地的黑暗开始侵袭这个房间。

那棵很大的、树叶都掉光了的梧桐树还在夜风中挥舞它的枝桠。


有一个长度为 的序列,第 个位置上有权值 和能量值

一开始你的能量值,疲劳值和贡献值均为 ,可以从序列上的任意位置出发。

假定当前你位于第 个位置,拥有 的能量值,疲劳值为 ,那么可以获得 的贡献值。

接着,你可以同时对自己的能量值和疲劳值分别进行操作: ,也可以不操作。

然后,在 并且 的时候,你可以移动到 的位置,并使得疲劳值 ,也可以不移动,然后结束所有操作。

请求出从某个点出发的最大贡献值之和。

输入格式

第一行一个整数 ,表示序列长度为

接下来 行,每行两个整数 ,分别表示每个位置上的权值和能量值。

输出格式

一行一个整数,表示最大的贡献值之和为多少。

样例

样例输入 1

3
2 2
2 1
3 1

样例输出 1

3

样例输入 2

9
1 3
4 2
5 3
1 2
2 2
3 3
4 2
2 2
5 1

样例输出 2

8

样例输入 3

8
1 1
7 1
1 1
5 2
1 1
3 3
6 1
1 2

样例输出 3

11

数据范围与提示

样例解释

样例一解释:

从第 个位置出发的最大贡献值之和是:

从第 个位置出发的最大贡献值之和是:

从第 个位置出发的最大贡献值之和是:

故最大的贡献值是

样例二解释:

一种可以使贡献值之和最大的方案是:

数据范围

本题采用捆绑测试

  • Subtask 1(5 pts):保证
  • Subtask 2(15 pts):保证
  • Subtask 3(10 pts):
  • Subtask 4(15 pts):
  • Subtask 5(20 pts):
  • Subtask 6(20 pts):
  • Subtask 7(15 pts):无特殊限制。

对于所有数据,