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

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

Условие

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

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

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

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

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

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

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

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

Ограничения

2 ≤ m, n ≤ 300;  − 10⁴ ≤ a_i,j ≤ 10⁴

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

№	Входной файл (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 сек
Входной файл:	elect.in		Ограничение памяти:	64 Мб
Выходной файл:	elect.out

Условие

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

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

Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы i-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере p_i условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.

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

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

Первая строка входного файла содержит целое число n - количество партий. Следующие n строк описывают партии. Каждая из этих строк содержит по два целых числа: v_i - количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и p_i, - взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена. Если партия является идеологически устойчивой, то p_i равно -1. Гарантируется, что хотя бы одно p_i не равно -1.

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

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

Ограничения

1 ≤ n ≤ 10⁵; 1 ≤ v_i, p_i ≤ 10⁶ (p_i может быть равно -1)

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

№	Входной файл (elect.in)	Выходной файл (elect.out)
1	3 7 -1 2 8 1 2	6 3 3 3 4

---