25589번 - 푸앙이와 코인

문제

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

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

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

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

입력

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

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

출력

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

제한

힌트