재환이는 사탕에 중독된 아이이다.

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

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

각 박스에는 들어있는 사탕의 개수가 겉에 적혀져 있다.

대회의 참가자는 박스를 하나 고른다. 그 다음, 그 박스 안에 있는 사탕을 모두 가져가게 된다.

박스를 고르면, 고른 박스의 바로 위쪽 행과 바로 아래쪽 행에 있는 모든 박스,

그리고 고른 박스의 왼쪽과 오른쪽에 있는 박스에 들어있는 사탕이 모두 사라지게 된다.

참가자는 사탕이 들어있는 박스가 없을 때까지 박스를 고를 수 있다.

아래 그림을 살펴보자.

각 칸은 박스에 들어있는 사탕의 개수를 나타낸다.

각각의 단계에서 참가자가 고른 박스는 동그라미로 표시되어 있고, 회색으로 칠해진 박스는 참가자의 선택 때문에 사탕이 사라질 박스이다.

총 여덟 단계가 지나면 게임은 끝나게 되고, 재환이는 총 10+9+8+3+7+6+10+1 = 54개의 사탕을 가져가게 된다.

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

사탕줍기 timer 1s memory 128MB

사탕줍기 1s 128MB