Maximize Bowling Score Through Reordering

JYY has just completed a bowling match. In a standard bowling match there are \(n\) rounds (plus an extra bonus round if applicable). In each round there are 10 pins set up on the other end of the lane. In every round, the player is allowed up to two ball throws. The score of each ball is equal to the number of pins knocked down. In a round the base score equals the total number of pins knocked down in that round.

There are three kinds of rounds:

1. Strike: If the player knocks down all 10 pins on the first ball (i.e. scores 10), the round is a strike. In a strike round no second ball is thrown. Moreover, when computing the total match score, the entire base score (i.e. 10 plus any bonus) of the next round will be doubled.
2. Spare: If the player fails to knock down all 10 pins on the first ball but knocks down the remaining pins on the second ball (so the two-ball total is 10), the round is called a spare. In a spare round, when computing the total score, the first--ball score of the next round is doubled.
3. Miss: If after two throws the total pins knocked down is less than 10, the round is called a miss. No bonus is applied.

There is one more rule. If the original match (played in the given order) has a strike in round \(n\) (the last round), then an extra bonus round (\(n+1\) round) is played. In that case the bonus rule applies for the bonus round as well (its own score is doubled) but only once – even if the bonus round is a strike, no further rounds are played.

After finishing the match, JYY is unhappy with his score. He realizes that by reordering the rounds on his score sheet he can take advantage of the bonus–multiplying rule in a different way to achieve a higher total score. However, he does not want to be caught cheating – so if the original \(n\)th round was a strike then after reordering the \(n\)th round must still be a strike (so that an extra round is played) and if the original \(n\)th round was not a strike then the \(n\)th round in the new ordering must not be a strike.

Your task is to help JYY calculate the maximum score he can achieve by reordering his rounds subject to this constraint.

Scoring details:

• The base score of the match is the sum of the scores (pins knocked) in all rounds.
• Bonus is added as follows: For every round (except the final round) that is a strike, the base score of the next round is added again; for every round (except the final round) that is a spare, the first throw of the next round is added again; for a miss, no bonus is added.
• If an extra bonus round is played (because the original \(n\)th round was a strike) its score is doubled. Note that bonus effects do not cascade beyond the next round.

The reordering is done on the recorded rounds. Each round record contains the scores of the throws in that round. For a strike round, the record contains a single integer (10). For a spare or miss round it contains two integers (the first-ball score and the second-ball score). It is guaranteed that for a spare the two numbers add up to 10 and for a miss they add up to less than 10.

Input format summary:

• The first line contains the integer \(n\) — the number of rounds in the original match (not counting an extra bonus round, if any).
• Then follow \(n\) lines, each describing a round. For a strike round the line contains a single number 10. For a spare or miss round the line contains two integers separated by spaces.
• If the original \(n\)th round is a strike then an extra bonus round was played and one additional line follows describing that extra round.

Output format summary:

• Output a single integer — the maximum total score JYY can achieve by reordering his rounds while keeping the type of the original \(n\)th round unchanged.

Note: The base score (i.e. the sum of all round scores) remains invariant under reordering. The challenge is to choose an ordering that maximizes the total bonus based on pairing rounds appropriately. For a strike your bonus contribution comes from the total score (which is 10 in a strike round) of the following round, and for a spare it comes from the first-ball score of the following round.

inputFormat

The first line contains an integer \(n\) (the number of rounds, not counting the extra round if played).

Then follow \(n\) lines. Each line describes a round:

• If the line contains a single integer 10, it is a strike round.
• If the line contains two integers a b, it represents a round in which the player knocked down \(a\) pins on the first ball and \(b\) pins on the second ball. If \(a+b = 10\) it is a spare; otherwise, it is a miss.

If the \(n\)th round is a strike then an extra bonus round was played and one additional line follows describing that round (using the same format).

You may assume that \(n\) is small (as in a standard bowling game).

outputFormat

Output a single integer: the maximum possible total score after reordering the rounds subject to the constraint that the \(n\)th round remains of the same type as originally played.

sample

3
10
3 7
3 4

47

</p>