문제
재환이는 사탕에 중독된 아이이다.
재환이는 캔디 매거진의 열렬한 구독자이며, 올해 열리는 국제 사탕 줍기 대회에 한국 대표로 참가하게 되었다.
이 대회는 사탕을 포함하고 있는 박스가 M행 N열로 놓여 있는 곳에서 진행된다. (따라서 박스는 총 M × N개 있다)
각 박스에는 들어있는 사탕의 개수가 겉에 적혀져 있다.
대회의 참가자는 박스를 하나 고른다. 그 다음, 그 박스 안에 있는 사탕을 모두 가져가게 된다.
박스를 고르면, 고른 박스의 바로 위쪽 행과 바로 아래쪽 행에 있는 모든 박스,
그리고 고른 박스의 왼쪽과 오른쪽에 있는 박스에 들어있는 사탕이 모두 사라지게 된다.
참가자는 사탕이 들어있는 박스가 없을 때까지 박스를 고를 수 있다.
아래 그림을 살펴보자.
각 칸은 박스에 들어있는 사탕의 개수를 나타낸다.
각각의 단계에서 참가자가 고른 박스는 동그라미로 표시되어 있고, 회색으로 칠해진 박스는 참가자의 선택 때문에 사탕이 사라질 박스이다.
총 여덟 단계가 지나면 게임은 끝나게 되고, 재환이는 총 10+9+8+3+7+6+10+1 = 54개의 사탕을 가져가게 된다.
M과 N이 주어졌을 때, 재환이가 이 대회에서 가져갈 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 M과 N이 주어졌다. (1 ≤ M × N ≤ 100,000)
다음 M개 줄에는 박스에 들어있는 사탕의 개수 N개가 주어진다.
박스에 들어있는 사탕은 적어도 1개이며 1,000개를 넘지 않는다.
입력의 끝은 0 0 이다.
출력
각 테스트 케이스에 대해 재환이가 집을 수 있는 사탕의 최대 개수를 행 단위로 출력한다.
예제
5 5
1 8 2 1 9
1 7 3 5 2
1 2 10 3 10
8 4 7 9 1
7 1 3 1 6
4 4
10 1 1 10
1 1 1 1
1 1 1 1
10 1 1 10
2 4
9 10 2 7
5 1 1 5
0 0
54
40
17
출처
South America Regional Contests 2008 C
로그인해야 코드를 작성할 수 있어요.