Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

有一天 love_kd给萌萌哒学弟xkw出一道题 他给xkw一个n*n(n<=15)的棋盘,棋盘上每个格子上都放了一颗不同甜度的糖果 他说xkw只能取n个糖果 每个糖果的行和列都不能相同 xkw当然要让甜度和最高啦 可是他不知道怎么选糖果诶 所以只能求助于你啦

Input

此题有多组数据 每组数据第一行输入n(n<=15) 接下来n行 每行有n个不大于1000的正整数 代表棋盘格子上的糖果甜度

Output

对于每组数据 只需要输出 最高的甜度和即可

Sample Input

2 1 2 2 1 3 4 2 5 5 3 6 2 2 4

Sample Output

4 12

Author

xukaiwen