← 返回题目列表

AtCoder · abc306_d

G. 有毒全程

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

高桥决定享受一顿有线全餐,包括 N 餐厅的课程。
的 i- 第门课程是:

  • if X_i=0,一个 解毒剂 课程的美味 Y_i;
  • if X_i=1,一个 有毒 课程的美味 Y_i.

高桥吃完一道菜后,他的状态发生如下变化:

  • 最初,高桥的胃很健康。
  • 当他有 健康肠胃,
    • 如果他吃了 解毒剂 当然,他的胃 保持健康;
    • 如果他吃了 有毒 当然,他 胃部不适.
  • 当他有 胃部不适,
    • 如果他吃了 解毒剂 当然,他的胃 变得健康;
    • 如果他吃了 有毒 当然,他 去世.

膳食进展如下。

  • 重复以下过程 i = 1, \ldots, N 按此顺序。
    • 首先, i第道菜送给高桥。
    • 接下来,他选择是“吃”还是“跳过”课程。
      • 如果他选择“吃”它,他就会吃掉 i- 第门课程。 他的状态也会根据他吃的菜而改变。
      • 如果他选择“跳过”,他就不会吃 i- 第门课程。 这道菜不能稍后提供或以某种方式保留。
    • 最后,(如果他的状态改变,改变后)如果他没有死,
      • if i \neq N,他继续下一门课程。
      • if i = N,他活着走出了餐厅。

一个重要的会议正在等待着他,所以他必须活着离开那里。
找到 他吃的菜品的最大可能的美味总和 (或 0 如果他什么也没吃)当他决定在这种情况下是“吃”还是“跳过”课程时。

约束

  • 所有输入值均为整数。
  • 1 \le N \le 3 \times 10^5
  • X_i \in \{0,1\}
    • 换句话说, X_i 是 0 or 1.
  • -10^9 \le Y_i \le 10^9

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

输出

将答案打印为整数。


示例输入 1

5
1 100
1 300
0 -200
1 500
1 300

示例输出 1

600

以下选择导致他吃的菜品的总味道为 600,这是可能的最大值。

  • 他跳过了 1-st当然。 他现在有一个健康的胃。
  • 他吃了 2-当然。 他现在胃不舒服,他吃的菜的总味道相当于 300.
  • 他吃了 3-rd课程。 现在他的胃又恢复健康了,他吃的菜的总味道达到了 100.
  • 他吃了 4- 第门课程。 他现在胃不舒服,他吃的菜的总味道相当于 600.
  • 他跳过了 5- 第课程。 他现在胃不舒服。
  • 最后,他没有死,所以他活着走出了餐厅。

示例输入 2

4
0 -1
1 -2
0 -3
1 -4

示例输出 2

0

对于这个输入,最好什么都不吃,在这种情况下答案是 0.


示例输入 3

15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

示例输出 3

4100000000

答案可能不适合 32位整数类型。