G2048

В свободное от занятий время Гарри Поттер с друзьями очень любят играть в интеллектуальные игры и Гермиона принесла им новую игру. Ее игровое поле имеет форму квадрата размером 4х4. Перед первым ходом игры в некоторых двух разных произвольно выбранных клеточках находится по плитке номинала «2». Далее на каждом ходу в произвольно выбранной свободной клеточке появляется новая плитка номинала «2». Нажатием стрелки игрок может сдвинуть все плитки игрового поля в одну из четырех сторон (вверх/влево/вниз/вправо). Если при движении две плитки одного номинала «налетают» одна на другую, они сливаются в одну, номинал которой равняется сумме слитых. Например, если две плитки с номиналом «2» налетели друг на друга, они заменяются на одну плитку с номиналом «4» (2+2). При этом игровые очки увеличиваются на номинал вновь созданной плитки (в данном случае на 4). За один ход может выполниться несколько слияний и в этом случае все очки добавляются. Например, рассмотрим такое состояние игры:

Сдвиг влево в этом случае суммирует две «2» и две «8» и приносит 4+16=20 очков. После этого в случайной свободной клеточке появляется 2.

Гарри начал играть в предложенную игру, но очередные события, связанные с открытием Тайной комнаты, отвлекли его в самый разгар игры. Не узнав ничего нового, Гарри вернулся в свою комнату и решил продолжить игру. Однако после всех передряг он совсем забыл, сколько очков успел заработать. Теперь он просит Гермиону помочь ему по текущему состоянию игрового поля подсчитать, сколько очков он уже заработал.

Формат ввода-вывода:

Программа G2048 читает с клавиатуры (стандартного устройства ввода) четыре строки по четыре числа в каждом. Пустые клеточки обозначены нулями, непустые могут содержать только степени двойки, т.е. числа 2, 4, 8, 16, 32, …, 65536 таким образом, что поле в целом может быть правильной конечной или промежуточной позицией рассмотренной игры.

Программа G2048 выводит на экран (стандартное устройства вывода) единственное число – искомое количество очков.

Пример входных и выходных данных: