Bowling

JYY loves bowling. Although he is not very skilled, he always dreams of achieving a high score. Here, JYY introduces the rules of the special bowling tournament he participates in, and asks for your help to maximize his score.

Description

A bowling tournament consists of $N$ rounds, with 10 pins placed at the end of the lane in each round. In each round, the player has two attempts to knock down all 10 pins. For each attempt, the score is equal to the number of pins knocked down. The score for a round is the total number of pins knocked down in the two attempts.

For each round, there are three possible scenarios:

1. "Strike": If the player knocks down all 10 pins on the first attempt, the round is called a "Strike". In a "Strike" round, since all pins are knocked down on the first attempt, the player does not need to make a second attempt. Additionally, when calculating the total score, the player's score in the next round will be multiplied by 2 and added to the total.
2. "Spare": If the player knocks down all 10 pins using two attempts, the round is called a "Spare". Additionally, when calculating the total score, the player's score on the first attempt of the next round will be multiplied by 2 and added to the total.
3. "Miss": If the player fails to knock down all 10 pins after two attempts, the round is called a "Miss". Additionally, when calculating the total score, the player's score in the next round is added to the total without any multipliers.

Furthermore, if the $N$-th round is a "Strike", the player is allowed one additional round: that is, if the $N$-th round is a "Strike", the player will play a total of $N+1$ rounds. Obviously, in this case, the score of the $(N+1)$-th round will be doubled.

The additional round rule is applied only once. That is, even if the player gets a "Strike" in the $(N+1)$-th round, there will not be an $(N+2)$-th round. Therefore, the score of the additional round does not cause the scores of other rounds to be doubled.

Finally, the player's total score is the sum of the scores of each round after the additional round rule has been applied and scores have been doubled according to the rules above.

JYY has just finished an $N$-round bowling tournament, but he is very dissatisfied with his score.

JYY has come up with a plan: he can rearrange the order of all the rounds he played on his scorecard. Because of the doubling rules, he might be able to achieve a higher score!

Of course, JYY does not want to cheat; he wants to ensure that after the rearrangement, the number of rounds played remains the same as before: for example, if JYY got a "Strike" in the $N$-th round before the rearrangement, then after the rearrangement, the $N$-th round must still be a "Strike" to ensure the tournament consists of $N+1$ rounds; similarly, if JYY did not get a "Strike" in the $N$-th round, then after the rearrangement, the $N$-th round cannot be a "Strike".

Please help JYY calculate the maximum possible score he can achieve.

Input

The first line contains an integer $N$, representing the number of rounds in the bowling tournament.

The following $N$ or $N+1$ lines each contain two non-negative integers $x_i$ and $y_i$, representing the scores JYY obtained in the two attempts of that round, where $x_i$ is the score of the first attempt and $y_i$ is the score of the second attempt.

We use $x_i = 10, y_i = 0$ to represent a "Strike" round. The input data guarantees $x_i + y_i \le 10$.

There are $N+1$ lines of input if and only if $x_N = 10$ and $y_N = 0$.

Output

Output a single integer representing the maximum possible score JYY can achieve.

Examples

Input 1

2
5 2
10 0
3 7

Output 1

44

Note 1

Following the input order, JYY would get 37 points. The optimal strategy is to arrange the 3 rounds in the following order: 3 7 10 0 5 2

Constraints

• For 20% of the data, $N \le 9$.
• For 50% of the data, $N \le 20$.
• For 100% of the data, $N \le 50$.