시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB49426420055.866%

문제

N×M 크기의 물통이 있다. 이 물통의 각 칸은 높이가 다를 수도 있다. 이와 같은 물통에 물을 부었을 때, 담을 수 있는 물의 최대량을 계산하는 프로그램을 작성하시오. 물통의 테두리도 높이가 다를 수 있고, 테두리가 물통의 안쪽보다 높이가 낮을 수도 있다.

왼쪽 표는 물통의 높이를 나타낸 것이고, 오른쪽은 각 칸에 담은 물의 양을 나타낸 것이다. 이 경우가 답이 12로 최대인 경우가 된다.

입력

첫째 줄에 M, N(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 자연수로 각 칸의 높이가 주어진다. 각각의 높이는 1,000,000,000를 넘지 않는다.

출력

첫째 줄에 답을 출력한다. 답은 int 범위 이내이다. 이 값은 0이 될 수도 있다.

예제 입력 1

4 5
5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9

예제 출력 1

12
W3sicHJvYmxlbV9pZCI6IjIyNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiM2MgXHVjYzQ0XHVjNmIwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5OJnRpbWVzO00gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YmIzY1x1ZDFiNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJiM2NcdWQxYjVcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMmU0XHViOTdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViYjNjXHVkMWI1XHVjNWQwIFx1YmIzY1x1Yzc0NCBcdWJkODBcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWIyZjRcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiM2NcdWM3NTggXHVjZDVjXHViMzAwXHViN2M5XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWJiM2NcdWQxYjVcdWM3NTggXHVkMTRjXHViNDUwXHViOWFjXHViM2M0IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWIyZTRcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVkMTRjXHViNDUwXHViOWFjXHVhYzAwIFx1YmIzY1x1ZDFiNVx1Yzc1OCBcdWM1NDhcdWNhYmRcdWJjZjRcdWIyZTQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjBhZVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIGhlaWdodD1cIjIxOVwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA4XC93dC5QTkdcIiB3aWR0aD1cIjQ3OFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2N2NcdWNhYmQgXHVkNDVjXHViMjk0IFx1YmIzY1x1ZDFiNVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwIFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHViMmY0XHVjNzQwIFx1YmIzY1x1Yzc1OCBcdWM1OTFcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWIyZjVcdWM3NzQgMTJcdWI4NWMgXHVjZDVjXHViMzAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE0sIE4oMSAmbGU7IE4sJm5ic3A7TSAmbGU7IDMwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDEsMDAwLDAwMCwwMDBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJmNVx1Yzc0MCBpbnQgXHViYzk0XHVjNzA0IFx1Yzc3NFx1YjBiNFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAwXHVjNzc0IFx1YjQyMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIyNzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgV2VkZGluZyBKdWljZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIGNvd3MgaGF2ZSB0YWtlbiBhIHNpZGUgam9iIGRlc2lnbmluZyBpbnRlcmVzdGluZyBwdW5jaC1ib3dsIGRlc2lnbnMuIFRoZSBkZXNpZ25zIGFyZSBjcmVhdGVkIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSBmbGF0IGJvYXJkIG9mIHNpemUgVyBjbSB4IEggY20gaXMgcHJvY3VyZWQgKDMgJmx0Oz0gVyAmbHQ7PSAzMDAsIDMgJmx0Oz0gSCAmbHQ7PSAzMDApJm5ic3A7PFwvbGk+XHJcblx0PGxpPk9uIGV2ZXJ5IDEgY20geCAxIGNtIHNxdWFyZSBvZiB0aGUgYm9hcmQsIGEgMSBjbSB4IDEgY20gYmxvY2sgaXMgcGxhY2VkLiBUaGlzIGJsb2NrIGhhcyBzb21lIGludGVnZXIgaGVpZ2h0IEIgKDEgJmx0Oz0gQiAmbHQ7PSAxLDAwMCwwMDAsMDAwKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBibG9ja3MgYXJlIGFsbCBnbHVlZCB0b2dldGhlciBjYXJlZnVsbHkgc28gdGhhdCBwdW5jaCB3aWxsIG5vdCBkcmFpbiB0aHJvdWdoIHRoZW0uIFRoZXkgYXJlIGdsdWVkIHNvIHdlbGwsIGluIGZhY3QsIHRoYXQgdGhlIGNvcm5lciBibG9ja3MgcmVhbGx5IGRvbiYjMzk7dCBtYXR0ZXIhPFwvcD5cclxuXHJcbjxwPkZKJiMzOTtzIGNvd3MgY2FuIG5ldmVyIGZpZ3VyZSBvdXQsIGhvd2V2ZXIsIGp1c3QgaG93IG11Y2ggcHVuY2ggdGhlaXIgYm93bCBkZXNpZ25zIHdpbGwgaG9sZC4gUHJlc3VtaW5nIHRoZSBib3dsIGlzIGZyZWVzdGFuZGluZyAoaS5lLiwgbm8gc3BlY2lhbCB3YWxscyBhcm91bmQgdGhlIGJvd2wpLCBjYWxjdWxhdGUgaG93IG11Y2gganVpY2UgdGhlIGJvd2wgY2FuIGhvbGQuIFNvbWUganVpY2UgYm93bHMsIG9mIGNvdXJzZSwgbGVhayBvdXQgYWxsIHRoZSBqdWljZSBvbiB0aGUgZWRnZXMgYW5kIHdpbGwgaG9sZCAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIFcgYW5kIEgmbmJzcDs8XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uSCsxOiBMaW5lIGkrMSBjb250YWlucyByb3cgaSBvZiBib3dsIGhlaWdodHM6IFcgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGVhY2ggb2Ygd2hpY2ggcmVwcmVzZW50cyB0aGUgaGVpZ2h0IEIgb2YgYSBzcXVhcmUgaW4gdGhlIGJvd2wuIFRoZSBmaXJzdCBpbnRlZ2VyIGlzIHRoZSBoZWlnaHQgb2YgY29sdW1uIDEsIHRoZSBzZWNvbmQgaW50ZWdlcnMgaXMgdGhlIGhlaWdodCBvZiBjb2x1bW4gMiwgYW5kIHNvIG9uLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgbnVtYmVyIG9mIGNjJiMzOTtzIHRoZSBkZXNjcmliZWQgYm93bCB3aWxsIGhvbGQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+RmlsbC11cCB0aGUgdHdvIHNxdWFyZXMgb2YgaGVpZ2h0IDEgdG8gaGVpZ2h0IDUsIGZvciA0IGNjIGZvciBlYWNoIHNxdWFyZS4gRmlsbCB0aGUgc3F1YXJlIG9mIGhlaWdodCAyIHRvIGhlaWdodCA1LCBmb3IgMyBjYyBvZiBqb2ljZS4gRmlsbCB0aGUgc3F1YXJlIG9mIGhlaWdodCA2IHRvIGhlaWdodCA3IGZvciAxIGNjIG9mIGp1aWNlLiAyKjQgKyAzICsgMSA9IDEyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=