You are given a square grid with $n$ rows and $n$ columns, where each cell has a non-negative integer written in it. There is a chip initially placed at the top left cell (the cell with coordinates $(1, 1)$). You need to move the chip to the bottom right cell (the cell with coordinates $(n, n)$).

In one step, you can move the chip to the neighboring cell, but:

you can move only right or down. In other words, if the current cell is $(x, y)$, you can move either to $(x, y + 1)$ or to $(x + 1, y)$. There are two special cases:

if the chip is in the last column (cell $(x, n)$) and you're moving right, you'll teleport to the first column (to the cell $(x, 1)$);

if the chip is in the last row (cell $(n, y)$) and you're moving down, you'll teleport to the first row (to the cell $(1, y)$).

you cannot visit the same cell twice. The starting cell is counted visited from the beginning (so you cannot enter it again), and you can't leave the finishing cell once you visit it.

Your total score is counted as the sum of numbers in all cells you have visited. What is the maximum possible score you can achieve?


-----Input-----

The first line contains the single integer $n$ ($2 \le n \le 200$) — the number of rows and columns in the grid.

Next $n$ lines contains the description of each row of the grid. The $i$-th line contains $n$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, n}$ ($0 \le a_{i, j} \le 10^9$) where $a_{i, j}$ is the number written in the cell $(i, j)$.


-----Output-----

Print one integer — the maximum possible score you can achieve.


-----Examples-----

Input
2
1 2
3 4
Output
8
Input
3
10 10 10
10 0 10
10 10 10
Output
80


-----Note-----

None

Difficulty: MEDIUM
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
a = []
s = 0
for i in range(n):
	x = list(map(int, input().split()))
	a.append(x)
	s += sum(x)
b = []
for i in range(n):
	b.append(a[i][n - i - 1])
print(s - min(b))


n = int(input())
s = 0
table = []
for i in range(n):
	numbers = list(map(int, input().split()))
	table.append(numbers)
	s += sum(numbers)
specific_nums = [table[i][n - 1 - i] for i in range(n)]
minimum_spec_num = min(specific_nums)
print(s - minimum_spec_num)


p = [*map(int, open(0).read().split())]
n = p[0]
g = p[1:]
print(sum(g) - min(g[n - 1:-1:n - 1]))


l = [*map(int, open(0).read().split())]
n = l[0]
o = l[1:]
print(sum(o) - min(o[n - 1:-1:n - 1]))


(n, p, sum, m) = (int(input()), [], 0, 10 ** 10)
for i in range(n):
	arr = [int(x) for x in input().split()]
	for a in arr:
		sum += a
	if arr[n - 1 - i] < m:
		m = arr[n - 1 - i]
	p.append(arr)
print(sum - m)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
summary = 0
minimal = -1
n = inp()
for i in range(n):
	j = inlt()
	if minimal == -1:
		minimal = j[-1]
	elif minimal > j[n - i - 1]:
		minimal = j[n - i - 1]
	summary += sum(j)
sys.stdout.write(str(summary - minimal))


n = int(input())
t = 0
min_diag = 100000000000
grid = []
for i in range(n):
	row = list(map(int, input().split()))
	grid.append(row)
	t += sum(row)
(r, c) = (0, n - 1)
while r < n:
	min_diag = min(min_diag, grid[r][c])
	c -= 1
	r += 1
print(t - min_diag)


k = int(input())
s = 0
a = []
for i in range(k):
	l = list(map(int, input().split()))
	a.append(l[k - i - 1])
	s += sum(l)
s -= min(a)
print(s)


import sys
rd = sys.stdin.readline
n = int(rd())
(summ, minn) = (0, -1)
for i in range(n):
	a = list(map(int, rd().split()))
	if minn == -1:
		minn = a[-1]
	else:
		minn = min(minn, a[n - i - 1])
	summ += sum(a)
print(summ - minn)


n = int(input())
ans = 0
new = []
for i in range(n):
	a = input().split(' ')
	a = [int(ia) for ia in a]
	new.append(a[n - 1 - 1 * i])
	ans += sum(a)
print(ans - min(new))


n = int(input())
arr = []
for i in range(n):
	arr.append([int(x) for x in input().split()])
s = 0
for i in range(n):
	s = s + sum(arr[i], start=0)
m = 10000000000000000
for i in range(n):
	m = min(m, arr[n - i - 1][i])
print(s - m)


sum = 0
n = int(input())
matrix = []
diagonals = []
for i in range(n):
	matrix.append(list(map(int, input().split())))
for i in range(n):
	diagonals.append(matrix[i][n - i - 1])
for i in range(n):
	for j in range(n):
		sum += matrix[i][j]
sum -= min(diagonals)
print(sum)


n = int(input())
lines = [list(map(int, input().split())) for i in range(n)]
total = 0
for line in lines:
	total += sum(line)
temp = []
for i in range(n):
	temp.append(lines[i][n - i - 1])
total -= min(temp)
print(total)


(lst, antidiag) = ([], [])
n = int(input())
for i in range(n):
	a = list(map(int, input().split()))
	antidiag.append(a[n - 1 - i])
	lst.append(a)
mindiag = min(antidiag)
ans = 0
for i in lst:
	ans += sum(i)
print(ans - mindiag)


import sys
import math

def solve():
	n = int(input())
	a = [[int(x) for x in input().split()] for _ in range(n)]
	sum = 0
	mn = 2000000000.0
	for i in range(n):
		for j in range(n):
			sum += a[i][j]
	i = 0
	j = n - 1
	t = n
	while t > 0:
		mn = min(mn, a[i][j])
		i += 1
		j -= 1
		t -= 1
	print(sum - mn)
solve()


def fun(l):
	min = l[-1][0]
	for j in range(len(l)):
		if min > l[-1 - j][j]:
			min = l[-1 - j][j]
	ans = 0
	for i in range(len(l)):
		for j in range(len(l)):
			ans = ans + l[i][j]
	ans = ans - min
	print(ans)
ls = []
l = []
n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	ls.append(l)
	l = []
fun(ls)


n = int(input())
num = []
ans = 0
for i in range(n):
	x = list(map(int, input().split()))
	num.append(x)
for i in num:
	ans += sum(i)
x = num[0][n - 1]
for i in range(n):
	x = min(x, num[i][n - i - 1])
ans -= x
print(ans)


n = int(input())
ret = []
res = 0
mr = float('inf')
for x in range(n):
	ret.append(list(map(int, input().split())))
	mr = min(mr, ret[-1][n - x - 1])
	res += sum(ret[-1])
print(res - mr) if n != 1 else print(ret[0][0])


n = int(input())
grid = [[int(x) for x in input().split()] for _ in range(n)]
agg = sum((sum(grid[i]) for i in range(n)))
p = min((grid[i][-(i + 1)] for i in range(n)))
print(agg - p)


from math import ceil, sqrt
n = int(input())
grid = [[*map(int, input().split())] for i in range(n)]
m = min((grid[i][::-1][i] for i in range(n)))
s = sum((sum(i) for i in grid))
print(s - m)


import sys
s = sys.stdin.read()

def solve(cell_data, n):
	result = sum(cell_data)
	select_cell = cell_data[n - 1:-1:n - 1]
	find_lowest_cell = min(select_cell)
	result = result - find_lowest_cell
	print(result)
lines = s.split('\n')
cell_data = []
for line in lines[1:-1]:
	row_data = [int(i) for i in line.split()]
	cell_data.extend(row_data)
n = len(row_data)
solve(cell_data, n)


n = int(input())
count = 0
a = float('inf')
for i in range(n):
	b = list(map(int, input().split()))
	count += sum(b)
	a = min(a, b[n - 1 - i])
print(count - a)


n = int(input())
map_ = []
for i in range(n):
	map_.append(list(map(lambda x: int(x), input().split(' '))))
diag_arr = []
for i in range(n):
	diag_arr.append(map_[i][n - i - 1])
total = 0
for row in map_:
	total += sum(row)
min_ = min(diag_arr)
print(total - min_)


n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
print(sum((sum(i) for i in arr)) - min((arr[i][-(i + 1)] for i in range(n))))


def f(L, S):
	return L - min(S)
N = int(input())
S = []
L = 0
for i in range(N):
	y = list(map(int, input().split()))
	L += sum(y)
	S.append(y[N - i - 1])
print(f(L, S))


def main():
	maxsum = 0
	sq = []
	n = int(input(''))
	for i in range(n):
		l = input().split(' ')
		li = [int(x) for x in l]
		sq.append(li)
		maxsum += sum(li)
	maxsum -= min([sq[i][n - 1 - i] for i in range(n)])
	print(maxsum)
main()


n = int(input())
arr = []
ans = 0
for i in range(n):
	a = list(map(int, input().split()))
	arr += [a]
	ans += sum(a)
i = 0
j = n - 1
mn = arr[i][j]
i += 1
j -= 1
while i < n and j >= 0:
	mn = min(mn, arr[i][j])
	i += 1
	j -= 1
print(ans - mn)


n = int(input())
if n < 2:
	print('Invalid input')
	exit(1)
a = []
for i in range(0, n):
	temp = []
	temp = list(map(int, input().split()))[:n]
	a.append(temp)
b = 1
x = []
for i in range(0, n):
	count = 0
	for j in range(0, n):
		x.append(a[i][n - b])
		count += 1
		b += 1
		if count == 1:
			break
y = min(x)
count2 = 0
sum1 = 0
for i in range(0, n):
	for j in range(0, n):
		if a[i][j] == y and count2 == 0:
			count2 += 1
			continue
		sum1 += a[i][j]
print(sum1)


tilematrix = []
n = int(input())
row = []
sum = 0
for j in range(n):
	row = input().split()
	for x in range(n):
		row[x] = int(row[x])
		sum += row[x]
	tilematrix.append(row)
diagonal = []
for l in range(n):
	diagonal.append(tilematrix[l][n - 1 - l])
answer = sum - min(diagonal)
print(answer)


n = int(input())
s = 0
mi = 10000000000
for i in range(1, n + 1):
	m = list(map(int, input().split()))
	s += sum(m)
	if m[len(m) - i] < mi:
		mi = m[len(m) - i]
print(s - mi)


num = int(input())
s = 0
list1 = []
for i in range(num):
	l = list(map(int, input().split()))
	list1.append(l[num - i - 1])
	s += sum(l)
s -= min(list1)
print(s)


n = int(input())
a1 = []
sum = 0
for j in range(0, n):
	s = input()
	x = [int(i) for i in s.split(' ')]
	a1.append(x)
for i in range(0, n):
	for j in range(0, n):
		sum = sum + a1[i][j]
small = sum
for i in range(0, n):
	small = min(small, a1[i][n - 1 - i])
print(sum - small)