시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 13 9 9 90.000%

문제

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

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

입력

첫째 줄에 M, N(1≤N, M≤300)이 주어진다. 다음 M개의 줄에는 N개의 자연수로 각 칸의 높이가 주어진다. 각각의 높이는 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+XHJcbjxwPjxpbWcgd2lkdGg9XCI0NzhcIiBoZWlnaHQ9XCIyMTlcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwOFwvd3QuUE5HXCIgXC8+PFwvcD5cclxuPHA+XHVjNjdjXHVjYWJkIFx1ZDQ1Y1x1YjI5NCBcdWJiM2NcdWQxYjVcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YjJmNFx1Yzc0MCBcdWJiM2NcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViMmY1XHVjNzc0IDEyXHViODVjIFx1Y2Q1Y1x1YjMwMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE0sIE4oMSZsZTtOLCBNJmxlOzMwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVhYzAxIFx1Y2U3OFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDEsMDAwLDAwMCwwMDBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzQwIGludCBcdWJjOTRcdWM3MDQgXHVjNzc0XHViMGI0XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDBcdWM3NzQgXHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFdlZGRpbmcgSnVpY2VyIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiYjMzk7cyBjb3dzIGhhdmUgdGFrZW4gYSBzaWRlIGpvYiBkZXNpZ25pbmcgaW50ZXJlc3RpbmcgcHVuY2gtYm93bCBkZXNpZ25zLiBUaGUgZGVzaWducyBhcmUgY3JlYXRlZCBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgZmxhdCBib2FyZCBvZiBzaXplIFcgY20geCBIIGNtIGlzIHByb2N1cmVkICgzICZsdDs9IFcgJmx0Oz0gMzAwLCAzICZsdDs9IEggJmx0Oz0gMzAwKSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5PbiBldmVyeSAxIGNtIHggMSBjbSBzcXVhcmUgb2YgdGhlIGJvYXJkLCBhIDEgY20geCAxIGNtIGJsb2NrIGlzIHBsYWNlZC4gVGhpcyBibG9jayBoYXMgc29tZSBpbnRlZ2VyIGhlaWdodCBCICgxICZsdDs9IEIgJmx0Oz0gMSwwMDAsMDAwLDAwMCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgYmxvY2tzIGFyZSBhbGwgZ2x1ZWQgdG9nZXRoZXIgY2FyZWZ1bGx5IHNvIHRoYXQgcHVuY2ggd2lsbCBub3QgZHJhaW4gdGhyb3VnaCB0aGVtLiBUaGV5IGFyZSBnbHVlZCBzbyB3ZWxsLCBpbiBmYWN0LCB0aGF0IHRoZSBjb3JuZXIgYmxvY2tzIHJlYWxseSBkb24mIzM5O3QgbWF0dGVyISZuYnNwOzxcL3A+XHJcblxyXG48cD5GSiYjMzk7cyBjb3dzIGNhbiBuZXZlciBmaWd1cmUgb3V0LCBob3dldmVyLCBqdXN0IGhvdyBtdWNoIHB1bmNoIHRoZWlyIGJvd2wgZGVzaWducyB3aWxsIGhvbGQuIFByZXN1bWluZyB0aGUgYm93bCBpcyBmcmVlc3RhbmRpbmcgKGkuZS4sIG5vIHNwZWNpYWwgd2FsbHMgYXJvdW5kIHRoZSBib3dsKSwgY2FsY3VsYXRlIGhvdyBtdWNoIGp1aWNlIHRoZSBib3dsIGNhbiBob2xkLiBTb21lIGp1aWNlIGJvd2xzLCBvZiBjb3Vyc2UsIGxlYWsgb3V0IGFsbCB0aGUganVpY2Ugb24gdGhlIGVkZ2VzIGFuZCB3aWxsIGhvbGQgMC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCBXIGFuZCBIJm5ic3A7PFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uSCsxOiBMaW5lIGkrMSBjb250YWlucyByb3cgaSBvZiBib3dsIGhlaWdodHM6IFcgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGVhY2ggb2Ygd2hpY2ggcmVwcmVzZW50cyB0aGUgaGVpZ2h0IEIgb2YgYSBzcXVhcmUgaW4gdGhlIGJvd2wuIFRoZSBmaXJzdCBpbnRlZ2VyIGlzIHRoZSBoZWlnaHQgb2YgY29sdW1uIDEsIHRoZSBzZWNvbmQgaW50ZWdlcnMgaXMgdGhlIGhlaWdodCBvZiBjb2x1bW4gMiwgYW5kIHNvIG9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG51bWJlciBvZiBjYyYjMzk7cyB0aGUgZGVzY3JpYmVkIGJvd2wgd2lsbCBob2xkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+RmlsbC11cCB0aGUgdHdvIHNxdWFyZXMgb2YgaGVpZ2h0IDEgdG8gaGVpZ2h0IDUsIGZvciA0IGNjIGZvciBlYWNoIHNxdWFyZS4gRmlsbCB0aGUgc3F1YXJlIG9mIGhlaWdodCAyIHRvIGhlaWdodCA1LCBmb3IgMyBjYyBvZiBqb2ljZS4gRmlsbCB0aGUgc3F1YXJlIG9mIGhlaWdodCA2IHRvIGhlaWdodCA3IGZvciAxIGNjIG9mIGp1aWNlLiAyKjQgKyAzICsgMSA9IDEyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==