Las Vegas — это простая в освоении настольная игра с бросанием кубиков. Игроки бросают кубики и размещают их в одном из казино, и игрок, у которого в казино больше всего кубиков, забирает его деньги, но только если у него нет ничьей! Игра идеально сочетает в себе удачу и стратегию, и в 2012 году была номинирована на премию Spiel des Jahres.
Фотография @denislargeron на BoardGameGeek
Рассмотрим игру с $n$ казино и $(m + 1)$ игроками. Вы — $(m + 1)$-й игрок, а все остальные игроки уже разместили (или решили не размещать) свои кубики в казино. Известно, что в $i$-м казино $j$-й игрок разместил $a_{i,j}$ кубиков.
Ваша задача — определить количество кубиков $b_i$, которое вы хотите разместить в $i$-м казино для каждого $1 \le i \le n$. После того как вы разместите свои кубики, победитель каждого казино определяется отдельно по следующему правилу:
- Сначала, если два или более игроков разместили одинаковое количество кубиков в этом казино, все их кубики в этом казино удаляются.
- После этого победителем в этом казино объявляется игрок с наибольшим количеством кубиков. Если в казино не осталось кубиков, победителя нет.
Например:
- Рассмотрим казино, в котором 7 игроков разместили 1, 2, 3, 3, 4, 4, 4 кубика соответственно. Сначала, так как есть два или более игроков с 3 или 4 кубиками, все их кубики удаляются, и оставшееся количество кубиков составляет 1, 2, 0, 0, 0, 0, 0 соответственно. Победителем в этом казино становится игрок с 2 кубиками.
- Рассмотрим казино, в котором 4 игрока разместили 2, 3, 2, 3 кубика соответственно. Сначала, так как есть два или более игроков с 2 или 3 кубиками, все их кубики удаляются, и оставшееся количество кубиков составляет 0, 0, 0, 0 соответственно. Так как в этом казино не осталось кубиков, победителя нет.
Ваша цель — выиграть в наибольшем количестве казино среди всех игроков. Точнее, пусть $w_i$ — количество казино, в которых победителем является игрок $i$, тогда должно выполняться $w_{m+1} \ge w_i$ для всех $1 \le i \le m$. Минимизируйте общее количество кубиков, которые вы размещаете во всех казино, достигая своей цели. То есть минимизируйте $\sum_{i=1}^{n} b_i$.
Входные данные
Имеется несколько тестовых случаев. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 100$), указывающее количество тестовых случаев. Для каждого тестового случая:
Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 50$), указывающих количество казино и количество игроков (кроме вас).
В следующих $n$ строках $i$-я строка содержит $m$ целых чисел $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 10^8$), где $a_{i,j}$ — количество кубиков в казино $i$, размещенных игроком $j$.
Гарантируется, что существует не более 3 тестовых случаев, для которых $n > 20$ или $m > 20$.
Выходные данные
Для каждого тестового случая выведите одну строку, содержащую $n$ целых чисел $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^9$), разделенных пробелом, где $b_i$ — количество кубиков, которые вы размещаете в казино $i$. Можно доказать, что при таких ограничениях на $b_i$ оптимальный ответ всегда существует. Если существует несколько оптимальных ответов, вы можете вывести любой из них.
Примеры
Пример 1
3 4 3 3 3 2 2 7 5 3 5 2 1 6 4 3 4 100 100 100 1 0 0 0 1 100 100 100 1 1 4 20 0 20 0
4 0 6 0 1 0 2 0
Примечание
Для первого примера вы являетесь победителем в казино 1 и 3, в то время как игрок 2 является победителем в казино 2 и 4.
Для второго примера вы являетесь победителем в казино 3, в то время как игрок 4 является победителем в казино 2. В казино 1 победителя нет.