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