차의 공격
시간 제한2초메모리 제한128 MB
N×N 격자판에 룩 두 개를 놓아, 두 룩 중 하나 이상에게 공격받는 칸들(룩이 놓인 칸은 제외)의 합을 최대로 만드는 문제입니다.
문제
N×N 격자로 이루어진 정사각형 게임판이 있다. 각 칸에는 정수가 하나씩 적혀 있다. 가장 왼쪽 위 칸의 좌표는 (1, 1), 가장 오른쪽 아래 칸의 좌표는 (N, N)이다. 첫 번째 좌표는 열 번호, 두 번째 좌표는 행 번호를 나타낸다.
이 게임판의 서로 다른 두 칸을 골라 차(車)를 하나씩 놓으려고 한다.
어떤 칸과 같은 행이나 같은 열에 차가 하나 이상 놓여 있으면, 그 칸은 차의 공격을 받는다. 단, 차가 놓인 칸 자체는 차의 공격을 받는 칸으로 보지 않는다.
게임판에 적힌 수들이 주어질 때, 차의 공격을 받는 칸들에 적힌 수의 합이 최대가 되도록 두 차를 배치하라. 그때의 최대합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(2 ≤ N ≤ 300)이 주어진다.
다음 N개의 줄에는 게임판에 적힌 수가 한 줄에 N개씩 공백으로 구분되어 주어진다. 모든 수는 0 이상 1,000 이하의 정수이다.
출력
두 차를 배치했을 때 차의 공격을 받는 칸들에 적힌 수의 합으로 만들 수 있는 최댓값을 출력한다.