Description

这天，小q在公园的小路上乱逛，突然他发现一个n*n的正方形大石板，大石板中的每一个小石板上都刻着一个数字，且同一排的小石板小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...