愉悦的矩阵

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一天,bLue 得到了一个 n*n 的矩阵,矩阵上每个位置 (i, j) 都有一定的愉悦值。

bLue 只能选择不在对角线(包括主对角线和副对角线)上的一个位置来获得愉悦值,他想知道他能获得的最大愉悦值是多少?

Input

输入数据有多组(数据组数不超过 100),到 EOF 结束。

对于每组数据:

  • 第 1 行输入一个整数 n (3 <= n <= 100),表示矩阵的行数和列数。
  • 接下来 n 行,每行包含 n 个用空格隔开的整数 Aij (0 <= Aij <= 10^5),表示 (i, j) 位置上所能提供的愉悦值。

Output

对于每组数据,在一行内输出一个整数,表示 bLue 能获得的最大愉悦值。

Sample Input

3
3 2 1
1 5 2
1 2 1

Sample Output

2

Hint

Source

【2016级ACM集训队第二次选拔赛】bLue