Кубик - 2

В последнее время настольные игры стали очень популярны. В нашу жизнь возвращаются как некогда забытые, так и новые увлекательные игры. К вам попала совершенно новая, уникальная настольная игра. Для игры нужен игральный кубик (его развертка приведена на рисунке) и прямоугольное игровое поле, разбитое на клетки. В каждой клетке поля написано целое число.

Играть могут несколько человек по следующим правилам:

1. Первым ходом игрок ставит кубик в левую верхнюю клетку поля на любую грань.
2. Каждым следующим ходом игрок переходит на соседнюю справа или снизу клетку, перекатывая кубик на любую из 4 соседних граней.
3. За каждый ход игрок получает K*A очков, где A - число, записанное в текущей клетке поля, K - цифра на той грани кубика, которой он стоит на игровом поле.
4. Игрок ходит, пока не окажется в нижней правой клетке поля. Тогда очки за все его ходы суммируются.
5. Когда один игрок закончил ходить, начинает ходить второй игрок и т.д.
6. Победитель - игрок, набравший больше всех очков.

По заданному игровому полю определите максимальную сумму очков, которую можно получить, играя по указанным правилам.

Входные данные

Первая строка входного файла INPUT.TXT содержит разделенные пробелом числа N и M - размеры игрового поля (1 ≤ N×M ≤ 10⁵). Далее идет N строк по M чисел, разделенных пробелами - числа, записанные в клетках игрового поля. Все числа по модулю не превышают 10³.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – наибольшее количество очков, которые можно получить при оптимальной игре.

Пример

Пояснение к примеру

Первоначально кубик следует установить на 6, далее вниз на 2, потом вниз на 6, вправо на 2 вправо на 6. Итого 6*1 + 2*(-4) + 6*7 + 2*(-8) + 6*9 = 78

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]