Антагонистическая игра
На каждой клетке шахматной доски размером 8×8 записано целое неотрицательное число. Двое игроков по очереди переставляют короля, перемещая его только вправо, вверх или по диагонали вправо-вверх. Первоначально король стоит в левом нижнем углу. Игра продолжается до тех пор, пока король не окажется в правой верхней клетке доски. Игрок, переставивший короля в некоторую клетку получает от другого игрока денежную сумму, равную числу, записанному в этой клетке.
Определите стоимость игры - сумму, которая окажется в конце игры у первого игрока, если первый игрок старается её максимизировать, а второй - минимизировать.
Входные данные
На вход программе подается восемь строк, каждая строка содержит восемь целых неотрицательных чисел, не превосходящих 1000. В левом нижнем углу всегда записано число 0.
Выходные данные
Выведите единственное число - стоимость игры.