In anticipation of the Olympiad, schoolchildren decided to have fun and play a game. They remembered their favorite game, 2048, which they played all the time in class. The guys took a sheet of paper and came up with entertainment based on their favorite game. The rules for it are very simple. The host thinks of some position from the game 2048 and writes it out on a sheet. The player who names the best move first wins. After a few rounds, you realized that there was no way you could win honestly, so you decided to go tricky and write a program that solves this puzzle for you.
Recall the rules of the game 2048. On the field 4 × 4 scattered are numbers that are powers of two from 2 to 1024, some cells may be empty. Each turn, the player can move all the tiles of the playing field in one direction. If, during a shift, two tiles of the same denomination "blow" one on the other, then they stick together into one, the value of which is equal to the sum of the connected tiles. For each connection, game points are increased by the face value of the resulting tile. A tile, obtained by sticking two others, can no longer participate in sticking.
Input
The program receives four lines as input, each of which contains four numbers. Numbers are powers of two from 2 to 1024. Some cells contain the number 0, which means that the cell is empty.
Imprint
Print a single number — the maximum number of points that can be obtained in one move from this position.
Examples
| # |
Input |
Output |
| 1 |
2 0 0 0
2 0 0 0
2 0 0 0
0 0 0 0
|
4
|
| 2 |
2 0 0 0
2 0 0 0
2 0 0 0
2 0 0 0
|
8
|
| 3 |
2 2 4 0
0 0 0 0
0 0 0 0
0 0 0 0
|
4
|
| 4 |
2 2 4 0
0 2 2 2
0 2 4 0
2 4 4 0
|
16
|
Notes
Please read this section carefully for a better understanding of the rules of the game.
The best answer on the first test is achieved by moving down.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0
The best answer for the second test is achieved by moving down.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0
The best answer for the third test is achieved by moving to the left.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0
The best answer for the fourth test is achieved by moving down.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2