В ожидании олимпиады школьники решили развлечься и поиграть в игру. Они вспомнили о своей любимой игре 2048, в которую постоянно играли на уроках. Ребята взяли лист бумаги и придумали себе развлечение на основе своей любимый игры. Правила в ней получились очень простыми. Ведущий загадывает какую-то позицию из игры 2048 и выписывает ее на лист. Игрок, который первым назовет наилучший ход, выигрывает. После нескольких раундов вы поняли, что выиграть по-честному у вас никак не выходит, поэтому вы решили пойти на хитрость и написать программу, решающую данную головоломку за вас.
Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.
Входные данные
Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.
Выходные данные
Выведите единственное число — максимальное количество очков, которое можно получить за один ход из данной позиции.
Примеры
| № |
Входные данные |
Выходные данные |
| 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
|
Примечания
Внимательно прочитайте этот раздел для лучшего понимания правил игры.
Наилучший ответ на первый тест достигается движением вниз.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0
Наилучший ответ на второй тест достигается движением вниз.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0
Наилучший ответ на третий тест достигается движением влево.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Наилучший ответ на четвертый тест достигается движением вниз.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2