Армия из n дроидов построена в один ряд. Каждый дроид описывается m целыми числами a1, a2, ..., am, где ai — количество деталей i-го типа в механизме этого дроида. R2-D2 хочет уничтожить максимальную по длине последовательность подряд идущих дроидов. У него есть m оружий, i-е из них способно за один выстрел уничтожить у всех дроидов в армии по одной детали i-го типа (если у дроида нет деталей этого типа, то ничего не происходит).
Дроид считается уничтоженным, когда уничтожены все его детали. R2-D2 может сделать не больше k выстрелов. Сколько выстрелов из оружия каждого типа нужно произвести R2-D2, чтобы уничтожить максимальную по длине последовательность подряд идущих дроидов?
В первой строке записано три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 5, 0 ≤ k ≤ 109) — количество дроидов, количество типов деталей и количество доступных выстрелов соответственно.
Далее идут n строк, описывающие дроидов. Каждая строка содержит m целых чисел a1, a2, ..., am (0 ≤ ai ≤ 108), где ai — количество деталей i-го типа у соответствующего робота.
Выведите через пробел m целых чисел, где i-е число — количество выстрелов из оружия i-го типа, которые нужно произвести, чтобы уничтожить максимальную по длине последовательность подряд идущих дроидов.
Если существует несколько оптимальных ответов — выведите любой.
Необязательно совершать ровно k выстрелов, можно совершить меньше.
5 2 4
4 0
1 2
2 1
0 2
1 3
2 2
3 2 4
1 2
1 3
2 2
1 3
В первом тесте будут уничтожены второй, третий и четвертый дроиды.
Во втором тесте будут уничтожены первый и второй дроиды.
| Codeforces Round 291 (Div. 2) |
|---|
| Закончено |
