문제
$N\times M$ 크기의 격자가 주어진다. $i$행 $j$열의 칸에는 음이 아닌 정수 $a_{ij}$가 적혀 있다. (1ドル\le i\le N$; 1ドル\le j\le M$)
민지는 각 차례마다 아래와 같은 행동을 한다.
- 격자에서 상하좌우로 인접한 두 칸을 선택한다. 이때 두 칸에 적힌 수 중 적어도 하나는 양의 정수이어야 한다.
- 선택한 칸에 적힌 수에서 1ドル$씩 뺀다. 만약 어떤 칸에 적힌 수가 0ドル$이라면 그대로 둔다.
모든 칸에 적힌 수가 0ドル$이 될 때 게임이 종료된다. 민지는 이 게임을 최대한 오래 하려고 한다. 민지가 최선을 다해 게임을 오래 진행했을 때, 진행할 수 있는 최대 차례의 수를 구해보자.
W3sicHJvYmxlbV9pZCI6IjM0MDUzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2M0XHViYmY4XHViMTc4IFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+JE5cXHRpbWVzIE0kIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjYTlcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkaSRcdWQ1ODkgJGokXHVjNWY0XHVjNzU4IFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCAkYV97aWp9JFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMmU0LiAoJDFcXGxlIGlcXGxlIE4kOyAkMVxcbGUgalxcbGUgTSQpPFwvcD5cclxuXHJcbjxwPlx1YmJmY1x1YzljMFx1YjI5NCBcdWFjMDEgXHVjYzI4XHViODQwXHViOWM4XHViMmU0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNTg5XHViM2Q5XHVjNzQ0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWFjYTlcdWM3OTBcdWM1ZDBcdWMxMWMgXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YjQ1MCBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzIxOCBcdWM5MTEgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTIwXHVkMGRkXHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4XHVjNWQwXHVjMTFjICQxJFx1YzUyOSBcdWJlODBcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWMyMThcdWFjMDAgJDAkXHVjNzc0XHViNzdjXHViYTc0IFx1YWRmOFx1YjMwMFx1Yjg1YyBcdWI0NTRcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Y2U3OFx1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4XHVhYzAwICQwJFx1Yzc3NCBcdWI0MjAgXHViNTRjIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuIFx1YmJmY1x1YzljMFx1YjI5NCBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWM2MjRcdWI3OTggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYmZjXHVjOWMwXHVhYzAwIFx1Y2Q1Y1x1YzEyMFx1Yzc0NCBcdWIyZTRcdWQ1NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzYyNFx1Yjc5OCBcdWM5YzRcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWM5YzRcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjYzI4XHViODQwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJE4kLCAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMiBcXGxlIE4sIE0gXFxsZSAxXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0ICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWNhOVx1Yzc5MFx1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRhX3tpMX0sIGFfe2kyfSwgXFxjZG90cywgYV97aU19JFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQwIFxcbGUgYV97aWp9IFxcbGUgMTBeOSQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjOWM0XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1Y2MyOFx1Yjg0MFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM0MDUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRG9taW5vIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGlzIGEgZ3JpZCBvZiBzaXplICROXFx0aW1lcyBNJC4gVGhlIGNlbGwgYXQgcm93ICRpJCwgY29sdW1uICRqJCBjb250YWlucyBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyICRhX3tpan0kLiAoJDFcXGxlIGlcXGxlIE4kOyAkMVxcbGUgalxcbGUgTSQpPFwvcD5cclxuXHJcbjxwPkVhY2ggdHVybiwgTWluamkgcGVyZm9ybXMgdGhlIGZvbGxvd2luZyBhY3Rpb25zLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPk1pbmppIHNlbGVjdHMgdHdvIGhvcml6b250YWxseSBvciB2ZXJ0aWNhbGx5IGFkamFjZW50IGdyaWQgY2VsbHMuIEF0IGxlYXN0IG9uZSBvZiB0aGUgdHdvIGNlbGxzIG11c3QgY29udGFpbiBhIHBvc2l0aXZlIGludGVnZXIuPFwvbGk+XHJcblx0PGxpPk1pbmppIGRlY3JlYXNlcyB0aGUgbnVtYmVyIGluIGVhY2ggc2VsZWN0ZWQgY2VsbCBieSAkMSQuIEhvd2V2ZXIsIGlmIHNvbWUgY2VsbCBjb250YWlucyAkMCQsIHNoZSBkb2VzIG5vdCBkZWNyZWFzZSB0aGF0IG51bWJlci48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGUgZ2FtZSBlbmRzIHdoZW4gZXZlcnkgY2VsbCBjb250YWlucyAkMCQuIE1pbmppIHdpc2hlcyB0byBwbGF5IHRoaXMgZ2FtZSBhcyBsb25nIGFzIHNoZSBjYW4uIEZpbmQgb3V0IHRoZSBtYXhpbXVtIG51bWJlciBvZiB0dXJucyB0aGUgZ2FtZSBjYW4gbGFzdCB3aGVuIE1pbmppIGRvZXMgaGVyIGJlc3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzICROJCBhbmQgJE0kLiAoJDIgXFxsZSBOLCBNIFxcbGUgMVxcLDAwMCQpPFwvcD5cclxuXHJcbjxwPlRoZW4sICROJCBsaW5lcyBmb2xsb3cuIFRoZSAkaSQtdGggb2YgdGhlbSBjb250YWlucyAkTSQgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRhX3tpMX0sIGFfe2kyfSwgXFxjZG90cywgYV97aU19JC4gKCQwIFxcbGUgYV97aWp9IFxcbGUgMTBeOSQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUsIHByaW50IHRoZSBtYXhpbXVtIG51bWJlciBvZiB0dXJucyB0aGUgZ2FtZSBjYW4gbGFzdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d