分数: 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位整数类型。