Description

这天，小q在公园的小路上乱逛，突然他发现一个正方形石板，石板上刻着一些数字，且同一排的石板小q发现可以乱换，这时，小q希望把每一排石板上刻的最大数字的石板放在和当前排相等的那一列，他想知道他这么放完，我这个正方形石板，正对角线的数字加起来是多少qwq，但他只有这个想法，居然不会算T_T，聪明的你可以帮帮小q吗？

简单来说，有一个n*n的石板，石板上刻着数字，对于每一排石板我可以随意排序，让你求最后石板正对角线可能的最大总和；

Format

Input

第一行输入一个n(1<=n<=200)  正方形石板的大小

接下来n行，每行n个数字 代表每个石板上刻的数字

Output

输出n*n的正方形石板正对角线总和的最大可能

Samples

3
3 2 1
2 3 1
1 2 3

9

Hint

小q真的好笨啊 O.o...