시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB136594741.228%

문제

$N\times N$ 크기의 격자 위에 칸마다 코인이 놓여 있다.

푸앙이는 격자 위에 한 변의 길이가 $1$이상 $N$이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.

그물은 반드시 $N\times N$ 크기의 격자 안에 완전히 포함되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.

푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오.

입력

첫 번째 줄에 정수 $N$ $(2 \le N \le 400)$이 주어진다.

두 번째 줄부터 $N$개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 $10^9$ 이하의 양의 정수이다.

출력

첫 번째 줄에 푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 출력한다.

예제 입력 1

2
1 2
3 4

예제 출력 1

5

예제 입력 2

4
3 5 1 8
10 4 6 7
9 10 12 1
2 11 13 5

예제 출력 2

39