Дедушка Тимура подарил ему шахматную доску, чтобы он попрактиковался. Эта доска \(a\) состоит из \(n\) строк и \(m\) столбцов. На каждой клетке написано неотрицательное целое число.
Задача Тимура поставить слона так, чтобы сумма на клетках, атакованных им, была максимальна. Слон атакует во всех направлениях по диагонали. Расстояние, на которое атакует слон, не ограничено. Обратите внимание, что клетка, в которой стоит слон, также считается атакованной. Помогите ему найти максимальную сумму, которую он может получить.
Выходные данные
Для каждого набора входных данных выведите одно число — максимальную сумму по всем возможным размещениям слона.
Примечание
В первом примере лучшая сумма достигается в этой позиции:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
|
20
1
5
3
|