Задача A. Максимальная сумма ≡

Автор:Седьмая Всероссийская Командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:max.in   Ограничение памяти:64 Мб
Выходной файл:max.out  

Условие

Сегодня на страницах газеты "Математический досуг" была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.

Для решения головоломки требуется найти такой невырожденный прямоугольник с вершинами в центрах ячеек таблицы, и сторонами, параллельными сторонам таблицы, чтобы сумма чисел, записанных в ячейках на границе получившегося прямоугольника, была максимальна.

Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.

Напишите программу, которая по заданной таблице найдет искомый прямоугольник.

Формат входного файла

На первой строке входного файла записаны два целых числа m и n. Далее следует описание таблицы - m строк, каждая из которых содержит по n целых чисел ai,j.

Формат выходного файла

На первой строке выходного файла выведите целое число s - максимальную сумму чисел на границе искомого прямоугольника. На второй строке выведите четыре натуральных числа: x1, y1, x2, y2 - координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь x - номер строки, а y - номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Ограничения

2 ≤ m, n ≤ 300;  − 104 ≤ ai,j ≤ 104

Примеры тестов

№ Входной файл (max.in) Выходной файл (max.out)
1 
2 3
1 1 1
1 1 1
 
6
1 1 2 3
2 
5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2
 
8
3 1 5 3

Задача B. Число ≡

Автор:Седьмая Всероссийская Командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:number.in   Ограничение памяти:64 Мб
Выходной файл:number.out  

Условие

Вася написал на длинной полоске бумаги большое число и решил похвастаться своему старшему брату Пете этим достижением. Но только он вышел из комнаты, чтобы позвать брата, как его сестра Катя вбежала в комнату и разрезала полоску бумаги на несколько частей. В результате на каждой части оказалось одна или несколько идущих подряд цифр.

Теперь Вася не может вспомнить, какое именно число он написал. Только помнит, что оно было очень большое. Чтобы утешить младшего брата, Петя решил выяснить, какое максимальное число могло быть написано на полоске бумаги перед разрезанием. Помогите ему!

Формат входного файла

Входной файл содержит одну или более строк, каждая из которых содержит последовательность цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.

Формат выходного файла

Выведите в выходной файл одну строку - максимальное число, которое могло быть написано на полоске перед разрезанием.

Ограничения

Количество строк во входном файле не превышает 100, каждая строка содержит от 1 до 100 цифр.

Примеры тестов

№ Входной файл (number.in) Выходной файл (number.out)
1 
2
20
004
66
 
66220004
2 
3
 
3
0.207s 0.016s 17