사탕 줍기 대회

상근이는 사탕에 중독된 아이이다. 상근이는 캔디 매거진의 열렬한 구독자이며, 올해 열리는 국제 사탕 줍기 대회에 한국 대표로 참가하게 되었다.

이 대회는 사탕을 포함하고 있는 박스가 M행 N열로 놓여져있는 곳에서 진행된다. (따라서 박스는 총 M × N개 있다) 각 박스에는 들어있는 사탕의 개수가 겉에 적혀져 있다.

대회의 참가자는 박스를 하나 고른다. 그 다음, 그 박스 안에 있는 사탕을 모두 가져가게 된다. 박스를 고르면, 고른 박스의 바로 위쪽 행과 바로 아래쪽 행에 있는 모든 박스, 그리고 고른 박스의 왼쪽과 오른쪽에 있는 박스에 들어있는 사탕이 모두 사라지게 된다. 참가자는 사탕이 들어있는 박스가 없을 때까지 박스를 고를 수 있다.

아래 그림을 살펴보자. 각 칸은 박스에 들어있는 사탕의 개수를 나타낸다. 각각의 단계에서 참가자가 고른 박스는 동그라미로 표시되어 있고, 회색으로 칠해진 박스는 참가자의 선택 때문에 사탕이 사라질 박스이다. 총 여덟 단계가 지나면 게임은 끝나게 되고, 상근이는 총 10+9+8+3+7+6+10+1 = 54개의 사탕을 가져가게 된다.

M과 N이 주어졌을 때, 상근이가 이 대회에서 가져갈 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 M과 N이 주어졌다. (1 ≤ M × N ≤ 105) 다음 M개 줄에는 박스에 들어있는 사탕의 개수 N개가 주어진다. 박스에 들어있는 사탕은 적어도 1개이며 103개를 넘지 않는다.

입력의 마지막 줄에는 0이 두 개 주어진다.

각 테스트 케이스에 대해 상근이가 집을 수 있는 사탕의 최대 개수를 출력한다.