AT_abc306_d [ABC306D] Poisonous Full-Course

题目描述

高桥君在餐厅里，决定享用由 $N$ 道菜组成的奇妙全套餐。
在这套菜单中，第 $i$ 道菜如下：

• 当 $X_i=0$ 时，是美味度为 $Y_i$ 的含解毒剂的菜肴。
• 当 $X_i=1$ 时，是美味度为 $Y_i$ 的含毒的菜肴。

高桥君在吃菜时，状态会发生如下变化：

• 最初，高桥君没有闹肚子。
• 当高桥君没有闹肚子时，
  • 吃含解毒剂的菜肴，状态保持没有闹肚子。
  • 吃含毒的菜肴，会闹肚子。
• 当高桥君闹肚子时，
  • 吃含解毒剂的菜肴，会恢复为没有闹肚子。
  • 吃含毒的菜肴，会死亡。

全套餐的流程如下：

• 对于 $i=1,\ldots,N$，依次进行以下操作：
  • 首先，第 $i$ 道菜被端上来。
  • 然后，高桥君可以选择“吃”或“让服务员撤下”这道菜。
    • 选择“吃”的话，高桥君会吃下第 $i$ 道菜，并根据菜肴类型改变状态。
    • 选择“撤下”的话，高桥君不会吃这道菜，且之后也无法再吃或保存这道菜。
  • 最后，（若状态发生变化则以变化后的状态为准）只要高桥君没有死亡，
    • 若 $i\neq N$，则进入下一道菜。
    • 若 $i=N$，则高桥君活着离开餐厅。

高桥君之后还有重要的工作，因此他必须活着离开餐厅。
在此条件下，请求出高桥君对每道菜选择“吃”或“撤下”时，所能获得的美味度总和的最大值（若什么都不吃，则为 $0$）。

输入格式

输入按以下格式从标准输入给出。

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

600

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 3 \times 10^5$
• $X_i \in \{0,1\}$
  • 即 $X_i$ 只能为 $0$ 或 $1$。
• $-10^9 \leq Y_i \leq 10^9$

样例解释 1

按照如下选择，可以使吃到的美味度总和达到 $600$，这是可能的最大值。

• 第 1 道菜选择撤下。高桥君没有闹肚子。
• 第 2 道菜选择吃。高桥君闹肚子，美味度总和为 $300$。
• 第 3 道菜选择吃。高桥君恢复为没有闹肚子，美味度总和为 $100$。
• 第 4 道菜选择吃。高桥君闹肚子，美味度总和为 $600$。
• 第 5 道菜选择撤下。高桥君闹肚子。
• 最终高桥君没有死亡，活着离开餐厅。

样例解释 2

在此输入下，什么都不吃是最优的，此时答案为 $0$。

样例解释 3

答案可能超出 $32$ 位有符号整数的范围。

由 ChatGPT 4.1 翻译