C. Максимум на спирали
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Рассмотрим квадрат k × k, разделенный на единичные квадратики, причем k ≥ 3 и нечетно. Начиная от левой верхней клетки, будем красить клетки в следующем порядке: двигаемся сначала вправо, затем вниз, затем влево, затем вверх, затем опять вправо и так далее. При этом движение в одном направлении заканчиваем в одном из двух случаев: мы добрались до стенки квадрата, или следующая после следующей клетки уже покрашена. Всю покраску заканчиваем, если при движении в любом из направлений, не удается закрасить ни одной клетки. Фигуру, состоящую из закрашенных клеток, назовем спиралью.

Примеры спиралей для k = 3, 5, 7, 9 можно видеть на рисунке.

Имеется таблица n × m, в каждой ячейке которой находится число. Рассмотрим всевозможные спирали, образованные ячейками таблицы. Это означает, что мы рассматриваем спирали всевозможных размеров, которые не выходят за границы таблицы. Для каждой из спиралей найдем сумму чисел ячеек, из которых она образована. От вас требуется найти максимум из всех этих значений среди всех спиралей.

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

В первой строке записаны два целых числа n и m (3 ≤ n, m ≤ 500) — размеры таблицы.

В следующих n строках записано по m целых чисел, разделенных пробелами: j-ое число в i-ой строке aij ( - 1000 ≤ aij ≤ 1000) — число, записанное в j-ой ячейке i-ой строки таблицы.

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

Выведите одно число — максимальную сумму чисел среди всех спиралей.

Примеры
Входные данные
6 5
0 0 0 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1
Выходные данные
17
Входные данные
3 3
1 1 1
1 0 0
1 1 1
Выходные данные
6
Входные данные
6 6
-3 2 0 1 5 -1
4 -1 2 -3 0 1
-5 1 2 4 1 -2
0 -2 1 3 -1 2
3 1 4 -3 -2 0
-1 2 -1 3 1 2
Выходные данные
13
Примечание

В первом тестовом примере спираль с максимальной суммой будет покрывать все единички таблицы.

Во втором примере спираль может покрыть только шесть единичек.