JOI Decorations Maximization

JOI has N phone ornaments numbered from 1 to N. Some ornaments come with a hook that can be used to hang another ornament. Each ornament, if used, must be hung either directly on the phone or on the hook of another ornament. However, at most one ornament can be hung directly on the phone.

Each ornament has an associated joy value, which can be negative if JOI dislikes that ornament. When hanging a chain of ornaments, if an ornament is used to support another (i.e. it is not the last ornament in the chain), it must have a hook. In other words, if the chain has at least 2 ornaments, every ornament except the last one must have a hook. It is allowed to use no ornament at all.

Your task is to select a set of ornaments and decide an order in which to hang them (forming a chain connected to the phone) so that the total sum of joy values is maximized.

More formally, suppose you choose a chain of ornaments of length L (L ≥ 1). Let the ornaments in the chain be \(x_1, x_2, \dots, x_L\). Then the arrangement must satisfy:

• Ornament \(x_1\) is hung directly on the phone.
• For every \(1 \le i \le L-1\), ornament \(x_i\) must have a hook (so that it can support ornament \(x_{i+1}\)).

You are free to choose L = 0 (in which case the total joy is 0) or any L ≥ 1 that meets the above criteria. Compute the maximum total joy that can be achieved.

Note: A chain with just one ornament (L = 1) is always allowed (there is no hook requirement in that case).

inputFormat

The input begins with a line containing a single integer N (1 ≤ N ≤ 10⁵), the number of ornaments. Each of the next N lines contains two integers a and b, where a ((-10^9 \le a \le 10^9)) is the joy value of that ornament and b is either 0 or 1. Here, b = 1 indicates that the ornament has a hook, and b = 0 indicates that it does not.

outputFormat

Output a single integer: the maximum total joy that can be obtained.

sample

5
1 1
2 0
-1 1
3 1
-2 0

6