Условие:
Рассмотрим прямоугольную таблицу из n строк и m столбцов, такую, что 4 <= n и 7 <= m. В каждой ячейке этой таблицы находится одно целое, возможно отрицательное, число.
Множество ячеек этой таблицы будем называть "буквой A" с вершиной в ячейке (x, y) и высотой h, если ему принадлежат следующие ячейки:
-ячейка с координатами (x, y);
-ячейки с координатами (x + i, y + i) для i от 1 до h - 1 (правая диагональ);
-ячейки с координатами (x + i, y - i) для i от 1 до h - 1 (левая диагональ);
-ячейки, из горизонтального интервала высотой в одну ячейку, левый конец которого находится на левой диагонали, а правый на правой (горизонтальная палочка буквы A); интервал расположен строго ниже горизонтали x + 1 и строго выше горизонтали x + h - 1 (то есть выше него имеется непустое "отверстие", а ниже него есть непустые "ножки" буквы A).
Весом буквы A будем называть сумму чисел в её ячейках. Для лучшего понимания, ознакомьтесь со следующими примерами.
На первом рисунке представлены примеры множеств ячеек, являющиеся буквами A. Жёлтым выделена минимальная возможная буква A с вершиной в ячейке (1, 4) и высотой 4. Сумма чисел в её ячейках (вес) равна 13. Оранжевым выделена буква A с длинными ножками, вершиной в ячейке (1, 12), высотой 6, и весом 34. Зелёным выделена буква A с вершиной в ячейке (3, 7) и высотой 7. Сумма чисел в её ячейках равна 48, и это максимальный вес среди всех букв A для данной таблицы. Помимо этой буквы A, в таблице имеется ещё одна буква A веса 48.
На втором рисунке представлены примеры множеств ячеек, не являющихся буквами A. У самой левой из них нет "ножек" и она выродилась в "треугольник", у правой верхней нет "отверстия", у правой нижней нет ни того ни другого.
Все ячейки буквы A должны находиться в пределах таблицы.
Для заданной таблицы необходимо найти букву A, с максимальным весом среди всех букв A этой таблицы. В ответ следует вывести этот максимальный вес.
Формат ввода
В первой строке находятся через пробел два целых числа n и m — размеры таблицы, 4 <= n <= 500, 7 <= m <= 500.
В следующих n строках содержится по m чисел через пробел — содержимое ячеек таблицы. Все числа в таблице целые в пределах от -1000 до 1000 включительно.
Формат вывода
Вывести одно целое число — максимально возможный вес некоторого множества ячеек, образующего букву A в заданной таблице.
