Description

A bowling game has $n$ frames. In each frame, ten pins are set up at the end of the lane. The player has two rolls in each frame to try to knock down all ten pins. The score of each roll equals the number of pins knocked down in that roll. The score of a frame is the total number of pins knocked down in its two rolls.

For each frame, there are three cases:

1. "Strike": If the player knocks down all ten pins on the first roll, the frame is a "strike". Because all pins have fallen, there is no second roll in that frame. When computing the total score, the entire score of the next frame is counted twice (doubled).

2. "Spare": If the player uses both rolls to knock down all ten pins, the frame is a "spare". When computing the total score, the score of the first roll in the next frame is counted twice.

3. "Open frame": If the player fails to knock down all ten pins in two rolls, the frame is an "open frame". When computing the total score, the next frame’s score is added normally, with no doubling.

In addition, if frame $n$ is a "strike", the player plays one extra frame: that is, there are in total $n+1$ frames. In this case, the score of frame $n+1$ will definitely be doubled.

The extra-frame rule is applied at most once. That is, even if frame $n+1$ is also a "strike", there will be no frame $n+2$. Therefore, the extra frame will not cause any other frame’s score to be doubled. The final total score is the sum of all frame scores after applying the above doubling rules, including the extra frame if it exists.

JYY just played a game of $n$ frames, but he is very unhappy with his score. He came up with an idea: he can reorder the sequence of all the frames on the scoresheet. After reordering, due to the doubling rules, JYY may obtain a higher total score.

Of course, JYY does not want it to look too fake. He wants to keep the number of frames the same as before after reordering. For example, if the original frame $n$ was a "strike", then after reordering, frame $n$ must still be a "strike" so that there are $n+1$ frames in total. Similarly, if the original frame $n$ was not a "strike", then after reordering, frame $n$ must also not be a "strike". Please help JYY compute the maximum possible total score he can obtain.

Input Format

The first line contains an integer $n$, the number of frames in the bowling game.

Then there are $n$ or $n+1$ lines. The $i$-th line contains two non-negative integers $x_i, y_i$, representing JYY’s scores on the two rolls in that frame, where $x_i$ is the first roll and $y_i$ is the second roll.

In particular, 10 0 represents a "strike".

There are $n+1$ lines if and only if $x_n = 10$ and $y_n = 0$.

Output Format

Output a single integer: the maximum total score JYY can obtain.

2
5 2
10 0
3 7

44

Hint

[Sample explanation] According to the input order, JYY will get $37$ points.
The best arrangement is:

3 7
10 0
5 2

Constraints
For 100% of the testdata, $1 \le n \le 50$.

Translated by ChatGPT 5