Обмін міняє місцями два завдання в одному рядку, тому кожен рядок вносить у стовпець рівно одне число, і рядки між собою незалежні. А оскільки масив мінімізується лексикографічно, стовпці треба обробляти зліва направо: спочатку якнайменший b_1, потім за фіксованого b_1 — якнайменший b_2, і так далі.
Один стовпець. Щоб зменшити b_1, у рядку достатньо одного обміну: поставити в перший стовпець найменше число цього рядка. Виграш дорівнює
і більше одного обміну на рядок для цього стовпця сенсу не має — менше за мінімум усе одно не буде. Тому з доступних обмінів вигідно витратити їх на рядки з найбільшими додатними виграшами: сортуємо g_i за спаданням і беремо перші \min(k, n).
Наступні стовпці. Після того як стовпець оброблено, число, що стоїть у ньому, фіксується — далі його чіпати не можна, інакше зіпсуємо вже мінімізований b_1. Тому для другого стовпця кожен рядок може привести найменше з-поміж незафіксованих чисел цього рядка, і все повторюється з рештою бюджету обмінів.
Звідси зручна реалізація. Для кожного рядка заздалегідь відсортуємо його значення й запам'ятаємо два відображення: яке за рангом число стоїть у кожному стовпці та в якому стовпці стоїть кожен ранг. Додатково тримаємо позначку «ранг уже зафіксовано» і вказівник на найменший незафіксований ранг — він рухається лише вперед, тому загальна робота з ним лінійна.
Тоді обробка стовпця виглядає так:
для кожного рядка беремо найменший незафіксований ранг і рахуємо виграш відносно того, що зараз стоїть у ;
збираємо додатні виграші, сортуємо за спаданням, застосовуємо перші \min(k, \cdot) обмінів (оновлюючи обидва відображення) і зменшуємо ;
фіксуємо ранги, що опинилися в , для всіх рядків.
Щойно вичерпано, решта стовпців залишається як є.
Складність — \mathcal{O}(nm \log n): сортування рядків на початку плюс сортування кандидатів у кожному з стовпців. Суми стовпців сягають 10^3 \cdot 10^6 = 10^9, тому виводьте їх у 64-бітному типі.