성적

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N×N 점수표에서 점수마다 50을 뺀 값을 더한 금액이 최대가 되도록 직사각형 부분표 하나를 지울 때의 최대 금액을 구합니다.

난이도: 보통10점 중 5점
유형: 행렬, 동적 계획법, 누적 합
정답자: 아직 제출이 없습니다

문제

주쿠는 학교에서 여러 번 시험을 봤고, 각 시험은 $0 \ldots 100$ 점 만점으로 채점되었다.

주쿠의 할아버지는 성적에 따라 용돈을 준다. 할아버지는 50점을 넘는 점수를 좋은 성적, 50점 미만인 점수를 나쁜 성적으로 본다. 구체적으로는 각 점수 중 50점을 넘는 부분은 용돈에 더하고, 50점에 못 미치는 부분은 용돈에서 뺀다. 예를 들어 점수가 35, 42, 81, 100이면 주쿠는 $(35-50)+(42-50)+(81-50)+(100-50) = -15-8+31+50 = 58$ 유로를 받는다. 정확히 50점인 시험은 용돈에 영향을 주지 않는다.

선생님은 주쿠의 점수를 $N$ 행 $N$ 열짜리 Excel 표에 기록하므로, 주쿠의 점수는 모두 $N^2$ 개다. 주쿠는 표에 한 번 접근할 수 있고, 성적을 고칠 수 있다. 직사각형 모양의 부분표를 하나 고르고(비어 있어도 되며, 즉 원소가 0개여도 된다) 그 안의 성적을 모두 지울 수 있다.

성적을 지운 뒤 주쿠가 받을 수 있는 용돈의 최댓값을 구하라.

입력

첫 줄에 정수 $N$ ( $2 \le N \le 300$ )이 주어진다. 선생님 표의 한 변 길이다.

다음 $N$ 개 줄에는 각각 공백으로 구분된 정수 $N$ 개가 $0$ 이상 $100$ 이하의 범위로 주어진다. 주쿠의 성적이다.

출력

주쿠가 받을 수 있는 용돈의 최댓값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
3
80 90 90
100 5 60
90 60 10
```
예상 출력
```
200
```

예제 2

입력

4
100 100 100 100
100 2 2 100
100 90 90 100
100 2 2 100

예상 출력