eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Черепаха

Черепаха

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb8360.gif

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

В первой строке заданы два натуральных числа n и m (1n, m1000) - число строк и столбцов плиток прямоугольного пола. В следующих n строках задано по m положительных чисел - количество ягод на соответствующей плитке.

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

В одной строке выведите номер плитки верхнего ряда (нумерация с 1), с которой надо начинать двигаться черепахе, чтобы съесть максимальное количество ягод, и количество ягод, которое она съест.

Пример

Входные данные #1
4 5
3 4 1 1 3
2 2 1 2 4
5 4 1 2 3
2 9 5 4 8
Выходные данные #1
2 20
Источник 2018 Azerbaijan School Competition, II Stage, April 8, Problem L