有毒全餐

题目描述

高桥君决定在一家餐厅享用由 $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

以下选择可使所吃菜的美味度之和达到最大值 $600$。

他跳过第 $1$ 道菜。此时他的胃是健康的。

他吃下第 $2$ 道菜。此时他的胃变得不舒服,所吃菜的美味度之和为 $300$。

他吃下第 $3$ 道菜。此时他的胃恢复健康,所吃菜的美味度之和为 $100$。

他吃下第 $4$ 道菜。此时他的胃变得不舒服,所吃菜的美味度之和为 $600$。

他跳过第 $5$ 道菜。此时他的胃不舒服。

最后,他没有死,所以平安走出了餐厅。

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

0

对于该输入,什么都不吃是最优的,此时答案为 $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$

提示

答案可能无法用 $32$ 位整数类型表示。