Problems
K Smallest Sums
K Smallest Sums
You're given k arrays, each array has k integers. There are kk
ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them.
Input
There are several test cases. The first line of each case contains an integer k (2 ≤ k ≤ 750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000.
Output
For each test case print in a separate line k smallest sums in ascending order.
Input example #1
3 1 8 5 9 2 5 10 7 6 2 1 1 1 2
Output example #1
9 10 12 2 2