题目描述

高桥决定到饭店去吃席。服务员会依次端上来 $N$ 道菜。

第 $i$ 道菜是：

• 若 $X_i = 0$，一道有解毒剂的菜，美味度是 $Y_i$；
• 若 $X_i = 1$，一道有毒的菜，美味度是 $Y_i$。

当高桥吃了一道菜之后，他的状态按照下述规则变化：

最初，高桥感觉良好。

当他感觉良好时，

• 若吃了一道有解毒剂的菜，他仍然感觉良好；
• 若吃了一道有毒的菜，他会肚子疼。

当他肚子疼时，

• 若吃了有解毒剂的菜，他会恢复感觉良好；
• 若吃了有毒的菜，他会死。

每道菜端上来时，高桥可以选择吃或不吃。

当然，高桥会确保自己活着走出饭店。

求高桥吃的菜的美味度之和的最大值。（若他什么也没吃，美味度之和是零。）

限制

输入的值都是整数

$1≤N≤3×10^5$

$X_i$ 是 0 或 1。

$−10^9≤Y_i≤10^9$

输入格式

$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