시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 136 34 33 25.781%

문제

동주는 항상 혼자 노느라 심심하다. 하지만 혼자놀기의 고수가 된 동주는 매일 매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느날 동주는 새로운 게임을 개발하였다. 그것은 점수 따먹기 라는 게임인데 그다지 재밌어 보이지는 않는다.

동주가 개발한 게임은 이렇다. 일단 N*M행렬을 그린다음 그 사이에 임의로 정수의 수를 쓴다. 그런 다음 직사각형을 그려 그 사이의 합으로 노는 게임이다. 

동주가 혼자 재밌게 놀던 중 지나가는 당신을 보고 당신을 붙잡고 게임을 하자고 한다. 귀찮은 당신은 직사각형을 그려 최대값을 구하여 빨리 동주에게서 벗어나고 싶다. 

입력

첫째 줄에 N(N<200) M(M<200)이 주어진다. 그 다음 N개의 줄게 M개씩 수가 입력이 들어온다.

출력

첫째 줄에 최대의 합을 출력하라.

예제 입력

3 5
2 3 -21 -22 -23
5 6 -22 -23 -25
-22 -23 4 10 2

예제 출력

16

힌트

출처

  • 문제를 번역한 사람: author9