Задача №115167. Игра джентльменов
\(n\) джентльменов играют в очень интересную игру: На столе перед ними лежат \(m\) карточек, на каждой по \(n\) чисел. \(j\)-е число на \(i\)-й карточке равно \(a_{i, j}\).
Джентльмены по очереди от \(1\)-го до \(n\)-го выбирают одну из оставшихся карточек и забирают её себе. После того как все закончили выбирать, \(j\)-й джентльмен получает столько очков, сколько написано на взятой им карточке на позиции \(j\).
Джентльмен, набравший наибольшее количество очков, считается победителем и получает главный приз. Также каждый джентльмен, включая победителя, получает вторичный приз, равный количеству набранных им очков.
Таким образом каждый джентльмен в первую очередь желает получить главный приз, который гораздо ценнее любого вторичного приза, а во вторую очередь хочет максимизировать количество набранных очков.
Вам предстоит по данному набору карточек узнать, какой из джентльменов получит главный приз, если все джентльмены будут играть оптимально.
В первой строке даны два целых числа \(n\), \(m\) \((2 \le n \le m \le 2\,000)\) — количество играющих джентльменов и число карточек соответственно.
В следующих \(m\) строках даны описания карточек. В каждой из них находятся \(n\) целых чисел \(a_{i, j}\) \((1 \le a_{i, j} \le n \cdot m)\) — числа на \(i\)-й карточке.
Гарантируется, что все числа \(a_{i, j}\) попарно различны.
В единственной строке выведите ответ на задачу — номер джентльмена, который заберет себе главный приз, если все джентльмены будут играть оптимально.
В первом примере \(1\)-й джентльмен может взять \(2\)-ю карточку, тем самым получив \(3\) очка. В таком случае на своем ходу \(2\)-й джентльмен сможет взять только \(1\)-ю или \(3\)-ю карточку, то есть получить \(1\) или \(2\) очка.
Во втором примере первый игрок точно не выиграет, так что берет себе первую карточку, чтобы максимизировать количество набранных очков для вторичного приза. Тогда что бы ни взял \(2\)-й игрок, \(3\)-й получит больше очков и победит.
2 3 4 1 3 6 5 2
1
3 3 3 9 8 2 4 7 1 6 5
3
3 4 2 7 1 9 12 5 4 3 8 11 6 10
2