Дана матрица, составленная из
неотрицательных целых чисел, имеющая N строк и M столбцов.
Необходимо найти в ней подматрицу с максимальной суммой граничных элементов.
Элемент матрицы считается граничным, если он находится в первой или последней
строке или в первом или последнем столбце.
Первая строка входного
файла
содержит целые числа N и M (2 <= N, M <= 200). Затем идёт N строк
по M чисел в каждой. Числа в строке разделены пробелом. Гарантируется,
что каждый элемент матрицы не превосходит 106.
Первая строка выходного
файла должна
содержать значение суммы граничных элементов в найденной подматрице. Во второй
строке выведите через пробел координаты левого верхнего и правого нижнего углов
найденной подматрицы. Первой координатой элемента является строка, а второй
столбец. Строки нумеруются от 1 до N сверху вниз, столбцы от 1 до M
слева направо. Если подходящих подматриц несколько, выведите любую.
Пример
|
STDIN
|
STDOUT
|
4 5
1 8 1 1 1
1 1 1 9 1
1 1 9 1 1
0 1 1 1 0
|
33
1 1 3 4
|
