守护学姐

Description

CSDN的刘畅学姐和渣哥两个傻逼又开始玩游戏了:在一个给定n*n矩阵中,每轮刘畅学姐先划掉一行,渣哥再划掉一列,两人各划的行列交叉点数值为刘畅学姐赢得渣哥的分数(赢得数据为负即为输给渣哥的分数),游戏直至矩阵被划完为止。现在聪明绝顶的你誓要守护学姐,请预判在某矩阵情况下,刘畅学姐能够赢得渣哥的最大分数(或输给渣哥的最少分数)。

Input

第一行为一个整数n(1<=n<=10),为矩阵的大小,接下来为该用例的矩形数值M(i,j)(-1000<=M(i,j)<=1000)

Output

输出刘畅学姐能赢得渣哥的最高总分数(即一个正数),如果刘畅学姐不能赢,则输出输给渣哥的最低总分数(即一个负数)。

Sample Input

2
10 10
-5 -5

Sample Output

5