[ABC306D] Poisonous Full-Course

## 题目描述 高桥君决定去一家诡异的饭店，享用包含 $ N $ 道菜的套餐。每道菜有两个属性 $ X, Y $，含义如下： - $ X_i = 0 $ 表示第 $ i $ 道菜**有解毒功效**； - $ X_i = 1 $ 表示第 $ i $ 道菜**有毒**； - $ Y_i $ 表示第 $ i $ 道菜的**美味程度**。 高桥君每品尝一道菜，他的身体状况就会发生如下的变化： - 起初，高桥君感到**舒适**。 - 当他感到**舒适**之时， - 如果他吃了一道**有解毒功效**的菜，他依然会感到**舒适**； - 如果他吃了一道**有毒**的菜，他就会感到**不适**。 - 当他感到**不适**之时， - 如果他吃了一道**有解毒功效**的菜，他就然会感到**舒适**； - 如果他吃了一道**有毒**的菜，他就会**当场去世**。 菜是一道一道上的，对于第 $ i $ 道菜，用餐流程如下： - 首先，上菜。 - 然后，高桥君可以选择**品尝**或选择**跳过**这道菜。 - 如果他选择**品尝**这道菜，他的身体状况就会随着前文提及的规则改变。 - 如果他选择**跳过**这道菜，这道菜不会留在餐桌上，之后也不会再上这道菜（即再也吃不到这道菜）。 - 在做出上述选择后，如果高桥君还活着， - 如果 $ i \neq N $，上第 $ i + 1 $ 道菜，继续上述流程。 - 如果 $ i = N $，高桥君就可以活着走出饭店。 高桥君还有一个重要的会议要开，所以他必须活着走出饭店。 现在，请你求出高桥君所品尝的菜肴的美味程度之和的最大值（如果他什么也不吃，我们认为答案为 $ 0 $）。 ## 说明/提示 - 保证输入的数均为整数。 - $ 1 \le N \le 3 \times 10^5 $ - $ X_i \in \{0, 1\} $ - 也就是说，$ X_i $ 要么为 $ 0 $，要么为 $ 1 $。 - $ -10^9 \le Y_i \le 10^9 $ ## 样例一解释 对于本组数据，如下的一系列选择可以使得高桥君所品尝的菜肴的美味程度之和达到最大值，即 $ 600 $。 - 他选择跳过第 $ 1 $ 道菜，此时他感到舒适。 - 他选择品尝第 $ 2 $ 道菜，此时他感到不适，他所品尝的菜肴的美味程度之和目前为 $ 300 $。 - 他选择品尝第 $ 3 $ 道菜，此时他又感到舒适，他所品尝的菜肴的美味程度之和目前为 $ 100 $。 - 他选择品尝第 $ 4 $ 道菜，此时他又感到不适，他所品尝的菜肴的美味程度之和目前为 $ 600 $。 - 他选择跳过第 $ 5 $ 道菜，此时他仍感到不适。 - 虽然他最后感到不适，但他还是活着走出了饭店。 ## 样例二解释 对于本组数据，高桥君可以选择什么也不吃，故答案为 $ 0 $。 ## 样例三解释 答案可能超出 $ 32 $ 位整数的范围。

[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 $ 番目の料理を食べない。この料理を後で提供してもらったり何らかの手段で保存したりすることはできない。 - 最後に、 (状態が変化するなら変化後の時点で) 高橋くんが死んでいない場合、 - $ i\ \neq\ N $ なら次の料理に進む。 - $ i\ =\ N $ なら高橋くんは生きて退店する。 高橋くんはこのあと重要な仕事があるため、高橋くんは生きて退店しなければなりません。 この条件の下で高橋くんが各料理に対し「食べる」「下げてもらう」を選択したとき、高橋くんが **食べた料理の美味しさの総和として考えられる最大値** ( 但し、何も食べなかった場合は $ 0 $ ) を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

答えを整数として出力せよ。

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

600

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

0

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

4100000000

### 制約 - 入力は全て整数 - $ 1\ \le\ N\ \le\ 3\ \times\ 10^5 $ - $ X_i\ \in\ \{0,1\} $ - つまり、 $ X_i $ は $ 0,1 $ のどちらかである。 - $ -10^9\ \le\ Y_i\ \le\ 10^9 $ ### Sample Explanation 1 以下のように選択することで食べた料理の美味しさの総和を $ 600 $ にでき、これが考えられる最大値です。 - $ 1 $ 番目の料理を下げてもらう。高橋くんはお腹を壊していません。 - $ 2 $ 番目の料理を食べる。高橋くんはお腹を壊し、食べた料理の美味しさの総和は $ 300 $ となります。 - $ 3 $ 番目の料理を食べる。高橋くんはお腹を壊していない状態に戻り、食べた料理の美味しさの総和は $ 100 $ となります。 - $ 4 $ 番目の料理を食べる。高橋くんはお腹を壊し、食べた料理の美味しさの総和は $ 600 $ となります。 - $ 5 $ 番目の料理を下げてもらう。高橋くんはお腹を壊しています。 - 最終的に高橋くんは死んでいないので、高橋くんは生きて退店する。 ### Sample Explanation 2 この入力の場合何も食べないことが最善ですが、この場合答えは $ 0 $ となります。 ### Sample Explanation 3 答えが $ 32 $ bit 符号付き整数に収まらない可能性があります。