Республиканская олимпиада по информатике, 2012 год, 9 класс

(Медкомиссия)

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Начался весенний призыв и военкоматы заполнились призывниками. Начальникам военкоматов поступил запрос о продолжительности проведения медкомиссий. Один из них обратился к Вам за помощью.
    Каждый из $N$ призывников должен пройти $M$ медицинских кабинетов. В одном кабинете одновременно могут осматривать только одного призывника. После завершения осмотра в $i$-м кабинете призывник мгновенно попадает в очередь в $i + 1$-й кабинет. Как только в каком-то кабинете освобождается место, его мгновенно заполняет призывник, стоящий первым в очереди в этот кабинет. После завершения осмотра в $M$-м кабинете призывник отправляется домой собирать вещи. Продолжительностью методкомиссии считается время между входом первого призывника в первый кабинет и выходом последнего призывника из $M$-го кабинета.
    Зная для каждого призывника время, которое он будет находиться в каждом кабинете (вы заранее обработали информацию из медицинской карточки), а также порядок входа в первый кабинет, определите продолжительность медкомиссии.

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

Первая строка входного файла содержит 2 целых числа $N$, $M$ $(1 \le N \le 10^5,$ $1 \le M \le 10).$ Каждая из следующих $N$ строк содержит по $M$ целых чисел, $j$-e число на $i$-й строке — время обследования $i$-гo призывника в $j$-м кабинете $(1 \le i \le N,$ $1 \le j \le M).$ Время — целое число в интервале от 1 до 1000. Призывники нумеруются в порядке входа в первый кабинет.

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

Выведите одно целое число — продолжительность проведения медкомиссии.

Примеры:

Вход

3 2
3 5
4 4
5 3

Ответ

15

Вход

3 1
3
4
5

Ответ

12