eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

K наименьших сумм

K наименьших сумм

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Имеются k массивов, каждый из которых содержит k целых чисел. Имеется k^k способов выбрать в точности один элемент из каждого массива и вычислить их сумму. Вам следует найти k наименьших сумм среди них.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит целое k (2k750). Каждая из следующих k строк описывает содержимое одного массива - k натуральных чисел. Каждое число не превосходит 1,000,000.

Выходные данные

Для каждого теста вывести в отдельной строке k наименьших сумм в возрастающем порядке.

Пример

Входные данные #1
3
1 8 5
9 2 5
10 7 6
2
1 1
1 2
Выходные данные #1
9 10 12
2 2