Кубик
В последнее время настольные игры стали очень популярны. В нашу жизнь возвращаются как некогда забытые, так и новые увлекательные игры. К вам попала совершенно новая, уникальная настольная игра. Для игры нужен игральный кубик (его развертка приведена на рисунке) и прямоугольное игровое поле, разбитое на клетки. В каждой клетке поля написано целое число.
Играть могут несколько человек по следующим правилам:
Первым ходом игрок ставит кубик в левую верхнюю клетку поля на любую грань.
Каждым следующим ходом игрок переходит на соседнюю справа или снизу клетку, перекатывая кубик на любую из 4 соседних граней.
За каждый ход игрок получает K·A очков, где A - число, записанное в текущей клетке поля, K - цифра на той грани кубика, которой он стоит на игровом поле.
Игрок ходит, пока не окажется в нижней правой клетке поля. Тогда очки за все его ходы суммируются.
Когда один игрок закончил ходить, начинает ходить второй игрок и т.д.
Победитель - игрок, набравший больше всех очков.
По заданному игровому полю определите максимальную сумму очков, которую можно получить, играя по указанным правилам.
Входные данные
Первая строка входного файла содержит T - количество тестов (T ≤ 200). Первая строка каждого теста содержит разделенные пробелом числа N и M - размеры игрового поля (1 ≤ N·M ≤ 10^5). Далее идет N строк по M чисел, разделенных пробелами - числа, записанные в клетках игрового поля. Все числа по модулю не превышают 10^3.
Выходные данные
Для каждого теста в отдельной строке вывести одно целое число – какое наибольшее количество очков можно получить при оптимальной игре.