Задачи
K наименьших сумм
K наименьших сумм
Имеются k массивов, каждый из которых содержит k целых чисел. Имеется k^k
способов выбрать в точности один элемент из каждого массива и вычислить их сумму. Вам следует найти k наименьших сумм среди них.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит целое k (2 ≤ k ≤ 750). Каждая из следующих 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