Лінивий студент#531

Лінивий студент

1 секунда
256 мегабайтів
Складна

Козак Вус — студент ВНЗ. У першому семестрі на нього чекає предметів та тижнів навчання. Вусу заздалегідь відомі всі завдання, і для зручності він оцінив їхню складність. Він склав таблицю розміром n \times m, де для -го предмета у -й тиждень потрібно виконати завдання складністю a_{i, j}. Зверніть увагу, що всі значення складності є попарно різними числами у всій таблиці.

Складністю тижня Вус називає сумарну складність завдань з усіх предметів у цей тиждень.

Вусу не вистачило канікул для відпочинку, тож він хоче хоча б на початку семестру не сильно напружуватися. На щастя, саме цього року студентам дозволили коригувати план навчання. У Вуса є можливість не більше разів виконати таку операцію: вибрати певний предмет та два різні тижні j_1 і j_2, після чого поміняти місцями завдання з цього предмета. Таким чином, у таблиці числа a_{i, j_1} та a_{i, j_2} обмінюються значеннями.

Мета Вуса — зробити так, щоб складність першого тижня була якомога меншою. Якщо таких варіантів декілька, він хоче мінімізувати складність другого тижня. Якщо ж і таких варіантів декілька — мінімізувати складність третього тижня, і так далі.

Більш формально, нехай b_j — це складність -го тижня:

b_j = a_{1, j} + a_{2, j} + \dots + a_{n, j}

Козак Вус хоче застосувати не більше операцій так, щоб результуючий масив тижневих складностей B = [b_1, b_2, \dots, b_m] став лексикографічно мінімальним. Допоможіть йому знайти цей масив.

Вхідні дані

Перший рядок містить три цілі числа , , (1 \le n, m \le 1000, 0 \le k \le 10^9) — кількість рядків, кількість стовпців та максимальна кількість операцій.

Наступні рядків містять по цілих чисел a_{i,j} (1 \le a_{i,j} \le 10^6, усі числа a_{i,j} попарно різні) — початкову таблицю.

Вихідні дані

Виведіть цілих чисел — лексикографічно найменший масив сум стовпців, який можна отримати після не більше ніж операцій.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

Для першого тестового прикладу:

Оскільки k = 1, можна виконати не більше однієї операції.

Початкові суми стовпців дорівнюють:

7 + 6 + 5 = 18,

1 + 8 + 2 = 11,

3 + 4 + 9 = 16.

Тобто початковий масив сум дорівнює [18, 11, 16].

Щоб отримати лексикографічно найменший масив, найкраще виконати операцію в першому рядку та поміняти місцями числа і .

Після цього таблиця матиме вигляд:

перший рядок: ,

другий рядок: ,

третій рядок: .

Суми стовпців дорівнюють:

1 + 6 + 5 = 12,

7 + 8 + 2 = 17,

3 + 4 + 9 = 16.

Отриманий масив [12, 17, 16] є лексикографічно найменшим з усіх варіантів, які можна отримати за одну операцію.

Для другого тестового прикладу:

Початкові суми стовпців дорівнюють:

9 + 2 + 5 = 16,

1 + 8 + 6 = 15,

7 + 3 + 11 = 21,

4 + 10 + 12 = 26.

Початковий масив сум дорівнює [16, 15, 21, 26].

Виконаємо операцію в першому рядку та поміняємо місцями числа і , після чого виконаємо другу операцію і поміняємо місцями числа і так само у першому рядку. Тоді отримаємо наступну таблицю:

Суми стовпців дорівнюють [8, 18, 21, 31].

Оцінювання

  1. ( бали): k=n\cdot m;

  2. ( балів): k=1, n=1;

  3. ( балів): n=1;

  4. ( балів): елементи у рядках початково відсортовані за спаданням;

  5. ( балів): k \le 10;

  6. ( балів): m=2;

  7. ( балів): n, m \le 100;

  8. ( балів): без додаткових обмежень.