After arriving at an island, the n survivors of the zombie apocalypse must work together to establish a base-center. There are n weapons and every survivor has more or less ability with each one. Your mission is to find a way to assign optimally the arsenal to the team. Input The input consists of several test cases. Each test case starts with a line that contains one integer n (1 ≤ n ≤ 100). The following n lines will contain n integers, say qij (0 ≤ qij ≤ 1000). Line number i will specify the ability of the survivor number i using each weapon j. Output For each test case print on a single line the maximum ability that can be obtained, when the weapons are optimally assigned. Sample Input 5 12730 34102 23600 06110 20045 2 13 59 2 16 59 Sample Output 23 10 11