시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 8 5 45.455%

문제

N×N 격자의 각 칸에 수가 하나씩 적혀 있는 정사각형 모양의 게임 보드가 있다. 편의상 가장 왼쪽 위 칸의 좌표를 (1, 1), 가장 오른쪽 아래 칸의 좌표를 (N, N)으로 생각한다. 첫 번째 좌표는 열 번호, 두 번째 좌표는 행 번호를 각각 나타낸다. 이 게임 보드에서 임의로 두 개의 칸을 골라 차(車)를 하나씩 놓으려고 한다. 물론 두 개의 칸은 서로 달라야 한다.

자신과 같은 열 또는 같은 행에 차(車)가 하나라도 놓여 있다면 그 칸은 "차의 공격을 받는 칸"에 해당된다. 하지만 차(車)가 직접 놓여 있는 칸은 "차의 공격을 받는 칸"에 해당되지 않는다.

게임 보드에 적혀 있는 수들이 주어지면, "차의 공격을 받는 칸"에 적혀 있는 수들의 합이 최대가 되도록 두 개의 차(車)를 배치하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2≤N≤300)이 주어진다. 이어서 N개의 줄에 걸쳐 게임 보드에 적혀 있는 수들이 한 줄에 N개씩 빈 칸을 사이에 두고 주어진다. 주어지는 수는 모두 0 이상 1,000이하의 정수이다.

출력

첫째 줄에, "차의 공격을 받는 칸"에 적혀 있는 수들의 합이 최대가 되도록 두 개의 차(車)를 배치했을 때 그 최대합을 출력한다.

예제 입력

3
0 1 4
3 0 2
1 4 1

예제 출력

15

힌트