시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1398 548 388 39.152%

문제

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

이 대회는 사탕을 포함하고 있는 박스가 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이 두 개 주어진다.

출력

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

예제 입력 1

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

예제 출력 1

54
40
17
W3sicHJvYmxlbV9pZCI6IjU3MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWQwZDUgXHVjOTBkXHVhZTMwIFx1YjMwMFx1ZDY4YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBhY1x1ZDBkNVx1YzVkMCBcdWM5MTFcdWIzYzVcdWI0MWMgXHVjNTQ0XHVjNzc0XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZTk0XHViNTE0IFx1YjllNFx1YWM3MFx1YzljNFx1Yzc1OCBcdWM1ZjRcdWI4MmNcdWQ1NWMgXHVhZDZjXHViM2M1XHVjNzkwXHVjNzc0XHViYTcwLCBcdWM2MmNcdWQ1NzQgXHVjNWY0XHViOWFjXHViMjk0IFx1YWQ2ZFx1YzgxYyBcdWMwYWNcdWQwZDUgXHVjOTBkXHVhZTMwIFx1YjMwMFx1ZDY4Y1x1YzVkMCBcdWQ1NWNcdWFkNmQgXHViMzAwXHVkNDVjXHViODVjIFx1Y2MzOFx1YWMwMFx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWIzMDBcdWQ2OGNcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYzE1XHVjMmE0XHVhYzAwIE1cdWQ1ODkmbmJzcDtOXHVjNWY0XHViODVjIFx1YjE5M1x1YzVlY1x1YzgzOFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LiAoXHViNTMwXHViNzdjXHVjMTFjIFx1YmMxNVx1YzJhNFx1YjI5NCBcdWNkMWQgTSAmdGltZXM7IE5cdWFjMWMgXHVjNzg4XHViMmU0KSBcdWFjMDEgXHViYzE1XHVjMmE0XHVjNWQwXHViMjk0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWM4OVx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzMDBcdWQ2OGNcdWM3NTggXHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1YmMxNVx1YzJhNFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVhY2UwXHViOTc4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWFkZjggXHViYzE1XHVjMmE0IFx1YzU0OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWFjMDBcdWM4MzhcdWFjMDBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWJjMTVcdWMyYTRcdWI5N2MgXHVhY2UwXHViOTc0XHViYTc0LCBcdWFjZTBcdWI5NzggXHViYzE1XHVjMmE0XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM3MDRcdWNhYmQgXHVkNTg5XHVhY2ZjIFx1YmMxNFx1Yjg1YyBcdWM1NDRcdWI3OThcdWNhYmQgXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViYzE1XHVjMmE0LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhY2UwXHViOTc4IFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWM2N2NcdWNhYmRcdWFjZmMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjMGFjXHViNzdjXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjYzM4XHVhYzAwXHVjNzkwXHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHViYzE1XHVjMmE0XHVhYzAwIFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHViYzE1XHVjMmE0XHViOTdjIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQ0IFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC4gXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWMwMCBcdWFjZTBcdWI5NzggXHViYzE1XHVjMmE0XHViMjk0IFx1YjNkOVx1YWRmOFx1Yjc3Y1x1YmJmOFx1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWQ2OGNcdWMwYzlcdWM3M2NcdWI4NWMgXHVjZTYwXHVkNTc0XHVjOWM0IFx1YmMxNVx1YzJhNFx1YjI5NCBcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggXHVjMTIwXHVkMGRkIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWMwYWNcdWQwZDVcdWM3NzQgXHVjMGFjXHViNzdjXHVjOWM4IFx1YmMxNVx1YzJhNFx1Yzc3NFx1YjJlNC4gXHVjZDFkIFx1YzVlY1x1YjM1ZiBcdWIyZThcdWFjYzRcdWFjMDAgXHVjOWMwXHViMDk4XHViYTc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWIwNWRcdWIwOThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjZDFkIDEwKzkrOCszKzcrNisxMCsxID0gNTRcdWFjMWNcdWM3NTggXHVjMGFjXHVkMGQ1XHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2FuZHkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzIycHg7IHdpZHRoOjYzM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1cdWFjZmMgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzc0IFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YzExYyBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBNXHVhY2ZjIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHViMmU0LiAoMSAmbGU7IE0gJnRpbWVzOyBOICZsZTsgMTA8c3VwPjU8XC9zdXA+KSBcdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzE1XHVjMmE0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWFjMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc0MCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1YWMxY1x1Yzc3NFx1YmE3MCAxMDxzdXA+MzxcL3N1cD5cdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzlkMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NzIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FuZHkgRGlzdHJpYnV0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgQ2hhcmxpZSBpcyBhIG5pY2UgYm95IGFkZGljdGVkIHRvIGNhbmRpZXMuIEhlIGlzIGV2ZW4gYSBzdWJzY3JpYmVyIHRvIEFsbCBDYW5kaWVzIE1hZ2F6aW5lIGFuZCB3YXMgc2VsZWN0ZWQgdG8gcGFydGljaXBhdGUgaW4gdGhlIEludGVybmF0aW9uYWwgQ2FuZHkgUGlja2luZyBDb250ZXN0LjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIGNvbnRlc3QgYSByYW5kb20gbnVtYmVyIG9mIGJveGVzIGNvbnRhaW5pbmcgY2FuZGllcyBhcmUgZGlzcG9zZWQgaW4gTSByb3dzIHdpdGggTiBjb2x1bW5zIGVhY2ggKHNvLCB0aGVyZSBhcmUgYSB0b3RhbCBvZiBNICZ0aW1lczsgTiBib3hlcykuIEVhY2ggYm94IGhhcyBhIG51bWJlciBpbmRpY2F0aW5nIGhvdyBtYW55IGNhbmRpZXMgaXQgY29udGFpbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBjb250ZXN0YW50IGNhbiBwaWNrIGEgYm94IChhbnkgb25lKSBhbmQgZ2V0IGFsbCB0aGUgY2FuZGllcyBpdCBjb250YWlucy4gQnV0IHRoZXJlIGlzIGEgY2F0Y2ggKHRoZXJlIGlzIGFsd2F5cyBhIGNhdGNoKTogd2hlbiBjaG9vc2luZyBhIGJveCwgYWxsIHRoZSBib3hlcyBmcm9tIHRoZSByb3dzIGltbWVkaWF0ZWx5IGFib3ZlIGFuZCBpbW1lZGlhdGVseSBiZWxvdyBhcmUgZW1wdGllZCwgYXMgd2VsbCBhcyB0aGUgYm94IHRvIHRoZSBsZWZ0IGFuZCB0aGUgYm94IHRvIHRoZSByaWdodCBvZiB0aGUgY2hvc2VuIGJveC4gVGhlIGNvbnRlc3RhbnQgY29udGludWVzIHRvIHBpY2sgYSBib3ggdW50aWwgdGhlcmUgYXJlIG5vIGNhbmRpZXMgbGVmdC48XC9wPlxyXG5cclxuPHA+VGhlIFx1ZmIwMWd1cmUgYmVsbG93IGlsbHVzdHJhdGVzIHRoaXMsIHN0ZXAgYnkgc3RlcC4gRWFjaCBjZWxsIHJlcHJlc2VudHMgb25lIGJveCBhbmQgdGhlIG51bWJlciBvZiBjYW5kaWVzIGl0IGNvbnRhaW5zLiBBdCBlYWNoIHN0ZXAsIHRoZSBjaG9zZW4gYm94IGlzIGNpcmNsZWQgYW5kIHRoZSBzaGFkZWQgY2VsbHMgcmVwcmVzZW50IHRoZSBib3hlcyB0aGF0IHdpbGwgYmUgZW1wdGllZC4gQWZ0ZXIgZWlnaHQgc3RlcHMgdGhlIGdhbWUgaXMgb3ZlciBhbmQgQ2hhcmxpZSBwaWNrZWQgMTAgKyA5ICsgOCArIDMgKyA3ICsgNiArIDEwICsgMSA9IDU0IGNhbmRpZXMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2FuZHkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzIycHg7IHdpZHRoOjYzM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBzbWFsbCB2YWx1ZXMgb2YgTSBhbmQgTiwgQ2hhcmxpZSBjYW4gZWFzaWx5IFx1ZmIwMW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjYW5kaWVzIGhlIGNhbiBwaWNrLCBidXQgd2hlbiB0aGUgbnVtYmVycyBhcmUgcmVhbGx5IGxhcmdlIGhlIGdldHMgY29tcGxldGVseSBsb3N0LiBDYW4geW91IGhlbHAgQ2hhcmxpZSBtYXhpbWl6ZSB0aGUgbnVtYmVyIG9mIGNhbmRpZXMgaGUgY2FuIHBpY2s/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIE0gYW5kIE4gKDEgJmxlOyBNICZ0aW1lczsgTiAmbGU7IDEwPHN1cD41PFwvc3VwPiksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgcmVzcGVjdGl2ZWx5LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyBOIGludGVnZXJzIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCBlYWNoIHJlcHJlc2VudGluZyB0aGUgaW5pdGlhbCBudW1iZXIgb2YgY2FuZGllcyBpbiB0aGUgY29ycmVzcG9uZGluZyBib3guIEVhY2ggYm94IHdpbGwgaGF2ZSBpbml0aWFsbHkgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAxMDxzdXA+MzxcL3N1cD4gY2FuZGllcy48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9lcyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgeW91ciBwcm9ncmFtIG11c3QgcHJpbnQgYSBzaW5nbGUgbGluZSwgY29udGFpbmluZyBhIHNpbmdsZSB2YWx1ZSwgdGhlIGludGVnZXIgaW5kaWNhdGluZyB0aGUgbWF4aW11bSBudW1iZXIgb2YgY2FuZGllcyB0aGF0IENoYXJsaWUgY2FuIHBpY2suPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Latin America > South America Regional Contests 2008 C번