AT_abc306_d [ABC306D] Poisonous Full-Course

[problemUrl]: https://atcoder.jp/contests/abc306/tasks/abc306_d 高桥君在餐厅里，决定享用由 $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 \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 翻译