Областная олимпиада школьников по информатике (личное первенство)

Наконец пять конкурсов завершились, и перед победителем популярного телевизионного шоу заветные двери, ведущие в сокровищницу. Перед сокровищницей расположено `N` длинных коридоров, все коридоры и сокровищница соединены между собой `M` дверьми, как показано на рисунке. Игрок находится в первом коридоре. Чтобы добежать до сокровищницы, у него всего `K` секунд. Если он не успеет за отведенное время добежать до нее, то он ничего не получает. Отчет времени начнется, когда он выберет одну из `M` дверей и станет перед ней. За секунду он может либо открыть дверь и перейти в следующий коридор, либо перейти к соседней двери в том же коридоре, слева или справа от текущей. Чтобы добраться до выигрыша в 1000000$, игрок должен пройти через `N` дверей. Но проблема не в том, чтобы открыть эти двери – замков на них нет, а в том, что на каждой двери написано некоторое число, и сумма чисел на дверях, через которые прошел игрок, будет вычтена из его выигрыша. Естественно, игрок хочет максимизировать свой выигрыш, и в этом ему должна помочь ваша программа.

В первой строке входного файла содержится три целых числа, разделенных пробелами – количество коридоров `N` (`1\ ≤\ N\ ≤\ 50`), количество дверей `M` (`1\ ≤\ M\ ≤\ 50`) и лимит времени игрока `K` (`N\ ≤\ K\ ≤\ M*(N-1)+1`). Далее следует `N` строк, в каждой строке `M` целых чисел в диапазоне от 1 до `1000000/N`, разделенных пробелами – числа на дверях. `j`-е число в `(i+1)`-й строке входного файла соответствует числу, написанному на `j`-й двери в `i`-м коридоре.

В первой строке выходного файла вывести `N` целых чисел, разделенных пробелами – номера дверей в порядке их прохождения игроком. Время прохождения не должно превышать `K` секунд, а сумма чисел на пройденных дверях минимальна.

4 5 6
250000 100000 150000 200000 200000
100000 150000 250000 100000 250000
150000 250000 100000 100000 1
250000 100000 250000 100000 100000

3 4 5 5