ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1029. Министерство

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Господин Ф. хочет, чтобы некоторый документ был подписан министром. Министр подписывает документ только в том случае, если он одобрен его министерством. Министерство представляет собой M-этажное здание с этажами, пронумерованными от 1 до M. На каждом этаже есть N кабинетов, пронумерованных от 1 до N. В каждом кабинете сидит ровно один чиновник.
Документ одобряется министерством только в том случае, если его подписывает хотя бы один чиновник с M-го этажа. Чиновник подписывает документ только при соблюдении хотя бы одного из следующих условий:
  1. чиновник работает на первом этаже;
  2. документ подписан чиновником, работающим в кабинете с таким же номером, но расположенном этажом ниже;
  3. документ подписан чиновником, работающим в соседнем кабинете (кабинеты соседние, если они расположены на одном этаже и их номера отличаются на единицу).
Каждый чиновник взимает плату за подписание документа. Плата представляет собой положительное целое число, не превышающее 109.
Вы должны найти самый дешевый способ одобрить документ в министерстве.

Исходные данные

Первая строка содержит целые числа M и N – количество этажей в здании и количество комнат на этаже (1 ≤ M ≤ 100; 1 ≤ N ≤ 500). Каждая из следующих M строк содержит N целых чисел, описывающих плату (j-е целое число в i-й строке – это плата, взимаемая чиновником, работающим в j-й комнате на i-м этаже).

Результат

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

Пример

исходные данныерезультат
3 4
10 10 1 10
2 2 2 10
1 10 10 10
3 3 2 1 1

Замечания

Вы можете считать, что для каждого чиновника всегда существует способ получить его подпись (пройдя от первого этажа до этого чиновника включительно), заплатив не более 109.
Автор задачи: Евгений Фролов
Источник задачи: III командный студенческий чемпионат Урала по программированию. 1999 г.