Loading [MathJax]/jax/output/SVG/jax.js

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


(Медкомиссия)
Ограничение по времени:
2 секунды
Ограничение по памяти:
64 мегабайта

Начался весенний призыв и военкоматы заполнились призывниками. Начальникам военкоматов поступил запрос о продолжительности проведения медкомиссий. Один из них обратился к Вам за помощью.
    Каждый из N призывников должен пройти M медицинских кабинетов. В одном кабинете одновременно могут осматривать только одного призывника. После завершения осмотра в i-м кабинете призывник мгновенно попадает в очередь в i+1-й кабинет. Как только в каком-то кабинете освобождается место, его мгновенно заполняет призывник, стоящий первым в очереди в этот кабинет. После завершения осмотра в M-м кабинете призывник отправляется домой собирать вещи. Продолжительностью методкомиссии считается время между входом первого призывника в первый кабинет и выходом последнего призывника из M-го кабинета.
    Зная для каждого призывника время, которое он будет находиться в каждом кабинете (вы заранее обработали информацию из медицинской карточки), а также порядок входа в первый кабинет, определите продолжительность медкомиссии.
Формат входного файла
Первая строка входного файла содержит 2 целых числа N, M (1N105, 1M10). Каждая из следующих N строк содержит по M целых чисел, j-e число на i-й строке — время обследования i-гo призывника в j-м кабинете (1iN, 1jM). Время — целое число в интервале от 1 до 1000. Призывники нумеруются в порядке входа в первый кабинет.
Формат выходного файла
Выведите одно целое число — продолжительность проведения медкомиссии.
Примеры:
Вход
3 2
3 5
4 4
5 3
Ответ
15
Вход
3 1
3
4
5
Ответ
12
посмотреть в олимпиаде

Комментарий/решение: