A few years after Trivial Pursuit became a hit, Canadian authors Pierre Berton and Charles Templeton created a rival trivia game called Tour De Force. Unfortunately, it never caught on because it wasn't a very good game.

Like Trivial Pursuit, Tour de Force has question cards but there are only two questions per card and each is worth a different number of points. On your turn, another player asks you the first question on your first card. If you get it right, you get the points and you have the option of trying the second follow-up question on the card (usually on the same subject). If you get that right, you get those points as well, and you have the option of taking another card and continuing. If at any point you get a question wrong, your turn is over, the card you are working on is discarded, and you lose a point. There is no penalty if you stop voluntarily. If you manage to answer $10$ questions in a row ($5$ cards), you score a "Tour de Force" and you win immediately.

For example, suppose the first card has questions worth $1$ and $3$ points. You get the first right and choose to go for the second one. You get that one right too and choose to take another card. Then on this card, the questions are worth $2$ and $4$ points. You answer the first correctly, and then try the second, but mess it up. Your total score is $5$ points for the turn ($1+3+2-1$). If you had chosen not to move on after the third question, you would have scored $6$ points. If you had answered the first question on the second card wrong, you would have scored $3$ points and the second card would have been discarded (meaning the $4$ point question would not be used on subsequent turns).

A smart Tour De Force player quits when they're ahead to avoid losing a point for the last question. But Bert is not a smart player. He always goes for a Tour De Force on every turn even though he has never once made it. Your task is to figure out the maximum possible score Bert can get (without scoring a Tour De Force) with any given set of cards.

For example, suppose there are $6$ question cards in the deck with pairs of point values [8 3], [4 5], [3 1], [2 2], [6 7], and [2 3] in that order. Then the maximum score Bert can get is $44$. He achieves this by going on a streak until the second question on the third card, then going on another streak to the end of the cards. This gets him $8+3+4+5+3-1+2+2+6+7+2+3=44$ points. Note that we are ignoring other players and assuming all $6$ cards are just for Bert.

The input consists of $10$ test cases. Each test case starts with an integer $N$ on a single line representing the number of cards in the case $(6\le N\le 1000)$. This is followed by $N$ lines for the cards in the order that they will appear in the game. Each line contains two integers representing the point values of the first and second question on the card, respectively (each question is worth between $1$ and $10$ points). Your program should output the maximum possible score Bert can get by following his strategy of never turning down a card or a question, assuming that he will never make it all the way to a Tour De Force. He can take as many turns as he likes to get through the cards, and can be in the middle of a turn when the cards run out.

Sample Input

10
7 1
4 1
3 8
4 6
2 2
4 3
4 5
10 6
8 6
7 2
6
4 4
7 5
2 4
8 1
9 3
5 7
9
2 6
2 8
3 1
6 3
7 4
2 6
1 10
9 9
7 1
8
2 9
1 6
10 3
9 6
6 2
9 9
2 5
4 1
7
4 8
7 1
1 1
3 3
7 3
6 3
3 8
8
6 8
1 2
10 4
7 7
10 8
5 8
8 5
3 10
6
4 9
4 5
8 4
9 3
8 10
10 10
9
6 2
9 9
5 4
10 8
3 7
4 1
2 1
8 6
4 8
8
1 4
10 1
1 10
7 2
8 5
3 3
6 6
5 10
6
1 8
7 6
9 10
1 3
10 7
7 8

Sample Output

87
57
82
81
56
94
80
92
79
73

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org