시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 39 8 4 15.385%

문제

남욱이는 계란을 N ×N크기의 계란판에 담아 판다. 신선도를 생명으로 여기는 남욱이는 각 계란을 썩음의 정도를 나타내는 썩음도로 표시한다. (썩음도가 클수록 더 썩은 계란이다.) 하지만 남욱이는 최근 열애를 하는 나머지 계란들이 방치돼 썩어버렸다. 남욱이는 어쩔 수 없이 K개의 가림판으로 썩은 계란들을 다음과 같은 규칙으로 가려서 계란판의 썩음도 합을 낮추려한다.

  • 각 가림판은 가로 혹은 세로로 인접한 두 계란을 가린다.
  • 가림판은 겹쳐질 수는 없지만, 닿을 수는 있다.
  • 모든 가려지지않은 계란들의 썩음도가 최소가 되도록 해야한다.

남욱이에게 규칙을 만족하면서 보이는 모든 계란의 썩음도 합을 얼만큼 낮출 수 있는지 알려주자.

입력

첫째 줄에는 계란판의 크기 N (1 ≤ N ≤ 2,000)와 가림판의 개수 K (1 ≤ K ≤ 8) 이 주어지며, 둘째 줄 부터 N + 1줄까지 각 줄마다 N개의 각 계란의 썩음도 F ( 0 ≤ F ≤ 1,000)가 주어진다.

출력

첫째 줄에 규칙을 만족하도록 보이는 모든 계란의 썩음도 합의 최솟값을 출력한다.

예제 입력 1

3 1
2 7 6
9 5 1
4 3 8

예제 출력 1

31

예제 입력 2

4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1

예제 출력 2

17

힌트

첫 번째 예제: 가림판을 썩음도 9와 5위에 놓는다.

두 번째 예제: 가림판을 [4, 5]와 [5, 4]에 놓는다.

W3sicHJvYmxlbV9pZCI6IjExNzc3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMGE4XHVjNmIxXHVjNzc0XHVjNzU4IFx1YzM2OVx1Yzc0MCBcdWFjYzRcdWI3ODBcdWQzMTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjBhOFx1YzZiMVx1Yzc3NFx1YjI5NCBcdWFjYzRcdWI3ODBcdWM3NDQgTiZuYnNwOyZ0aW1lcztOXHVkMDZjXHVhZTMwXHVjNzU4Jm5ic3A7XHVhY2M0XHViNzgwXHVkMzEwXHVjNWQwIFx1YjJmNFx1YzU0NCBcdWQzMTBcdWIyZTQuIFx1YzJlMFx1YzEyMFx1YjNjNFx1Yjk3YyBcdWMwZGRcdWJhODVcdWM3M2NcdWI4NWMgXHVjNWVjXHVhZTMwXHViMjk0Jm5ic3A7XHViMGE4XHVjNmIxXHVjNzc0XHViMjk0Jm5ic3A7XHVhYzAxIFx1YWNjNFx1Yjc4MFx1Yzc0NCZuYnNwO1x1YzM2OVx1Yzc0Y1x1Yzc1OCBcdWM4MTVcdWIzYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzM2OVx1Yzc0Y1x1YjNjNFx1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NWNcdWIyZTQuIChcdWMzNjlcdWM3NGNcdWIzYzRcdWFjMDAmbmJzcDtcdWQwNzRcdWMyMThcdWI4NWQgXHViMzU0IFx1YzM2OVx1Yzc0MCBcdWFjYzRcdWI3ODBcdWM3NzRcdWIyZTQuKSBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViMGE4XHVjNmIxXHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YWRmYyBcdWM1ZjRcdWM1NjBcdWI5N2MgXHVkNTU4XHViMjk0IFx1YjA5OFx1YmEzOFx1YzljMCBcdWFjYzRcdWI3ODBcdWI0ZTRcdWM3NzQmbmJzcDtcdWJjMjlcdWNlNThcdWIzZmMmbmJzcDtcdWMzNjlcdWM1YjRcdWJjODRcdWI4MzhcdWIyZTQuIFx1YjBhOFx1YzZiMVx1Yzc3NFx1YjI5NCBcdWM1YjRcdWNhNTQgXHVjMjE4IFx1YzVjNlx1Yzc3NCBLXHVhYzFjXHVjNzU4IFx1YWMwMFx1YjliY1x1ZDMxMFx1YzczY1x1Yjg1YyBcdWMzNjlcdWM3NDAgXHVhY2M0XHViNzgwXHViNGU0XHVjNzQ0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzNjXHViODVjIFx1YWMwMFx1YjgyNFx1YzExYyBcdWFjYzRcdWI3ODBcdWQzMTBcdWM3NTggXHVjMzY5XHVjNzRjXHViM2M0IFx1ZDU2OVx1Yzc0NCBcdWIwYWVcdWNkOTRcdWI4MjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhYzAxIFx1YWMwMFx1YjliY1x1ZDMxMFx1Yzc0MCBcdWFjMDBcdWI4NWMgXHVkNjM5XHVjNzQwIFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YWNjNFx1Yjc4MFx1Yzc0NCBcdWFjMDBcdWI5YjBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMFx1YjliY1x1ZDMxMFx1Yzc0MCBcdWFjYjlcdWNjZDBcdWM5YzggXHVjMjE4XHViMjk0IFx1YzVjNlx1YzljMFx1YjljYywgXHViMmZmXHVjNzQ0IFx1YzIxOFx1YjI5NCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWFjMDBcdWI4MjRcdWM5YzBcdWM5YzBcdWM1NGFcdWM3NDAgXHVhY2M0XHViNzgwXHViNGU0XHVjNzU4IFx1YzM2OVx1Yzc0Y1x1YjNjNFx1YWMwMCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWIwYThcdWM2YjFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYyZuYnNwO1x1YmNmNFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2M0XHViNzgwXHVjNzU4IFx1YzM2OVx1Yzc0Y1x1YjNjNCBcdWQ1NjlcdWM3NDQgXHVjNWJjXHViOWNjXHVkMDdjIFx1YjBhZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YjgyNFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2M0XHViNzgwXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOICgxICZsZTsgTiAmbGU7IDIsMDAwKVx1YzY0MCBcdWFjMDBcdWI5YmNcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IEsmbmJzcDsoMSAmbGU7IEsgJmxlOyA4KSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWI0NThcdWM5ZjggXHVjOTA0IFx1YmQ4MFx1ZDEzMCBOICsgMVx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IE5cdWFjMWNcdWM3NTggXHVhYzAxIFx1YWNjNFx1Yjc4MFx1Yzc1OCZuYnNwO1x1YzM2OVx1Yzc0Y1x1YjNjNCBGICggMCAmbGU7IEYgJmxlOyAxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWJjZjRcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YWNjNFx1Yjc4MFx1Yzc1OCBcdWMzNjlcdWM3NGNcdWIzYzQgXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjOiZuYnNwOzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFjMDBcdWI5YmNcdWQzMTBcdWM3NDQgXHVjMzY5XHVjNzRjXHViM2M0IDlcdWM2NDAgNVx1YzcwNFx1YzVkMCBcdWIxOTNcdWIyOTRcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWM6Jm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YWMwMFx1YjliY1x1ZDMxMFx1Yzc0NCBbNCwgNV1cdWM2NDAgWzUsIDRdXHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC48XC9zcGFuPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE3NzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJET01JTk8iLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIHJlY2VpdmVkIGFuIE4gJnRpbWVzOyBOIHRhYmxlIGZvciBoaXMgYmlydGhkYXksIHdoZXJlIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgaXMgd3JpdHRlbiBpbiBlYWNoIGZpZWxkIG9mIHRoZSB0YWJsZS4gVW5mb3J0dW5hdGVseSwgdGhlIHdyaXR0ZW4gbnVtYmVycyBhcmUgdG9vIGxhcmdlIGZvciBNaXJrbyZyc3F1bztzIHRhc3RlLCBzbyBoZSB3aWxsIHBsYWNlIEsgZG9taW5vZXMgb24gdG9wIG9mIHRoZSB0YWJsZSB0aGF0IHdpbGwgY292ZXIgdGhlIGZpZWxkcyB0aGF0IGFyZSB0b28gbGFyZ2UuPFwvcD5cclxuXHJcbjxwPk1vcmUgcHJlY2lzZWx5LCBNaXJrbyBwbGFjZXMgdGhlIGRvbWlub2VzIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmVhY2ggZG9taW5vIGNvdmVycyB0d28gZmllbGRzIG9mIHRoZSB0YWJsZSB0aGF0IGFyZSBhZGphY2VudCBpbiBhIHJvdyBvciBpbiBhIGNvbHVtbiw8XC9saT5cclxuXHQ8bGk+dGhlIGRvbWlub2VzIGRvIG5vdCBvdmVybGFwIChidXQgY2FuIHRvdWNoKSw8XC9saT5cclxuXHQ8bGk+dGhlIHN1bSBvZiBhbGwgdmlzaWJsZSAodW5jb3ZlcmVkKSBmaWVsZHMgbmVlZHMgdG8gYmUgYXMgc21hbGwgYXMgcG9zc2libGUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SXQgaXMgeW91ciB0YXNrIHRvIGRldGVybWluZSB0aGUgcmVxdWlyZWQgbWluaW1hbCBzdW0gb2YgdmlzaWJsZSBmaWVsZHMuIFRoZSB0ZXN0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgaXQgd2lsbCBhbHdheXMgYmUgcG9zc2libGUgdG8gcGxhY2UgSyBkb21pbm9lcyB3aXRob3V0IG92ZXJsYXBwaW5nLi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDIwMDApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgdGFibGUsIGFuZCBLICgxICZsZTsgSyAmbGU7IDgpLCB0aGUgbnVtYmVyIG9mIGRvbWlub2VzLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBOIGludGVnZXJzIGZyb20gdGhlIGludGVydmFsIFswLCAxMDAwXS4gVGhlc2UgTiAmdGltZXM7IE4gbnVtYmVycyBkZXNjcmliZSBNaXJrbyZyc3F1bztzIHRhYmxlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1pbmltYWwgc3VtIG9mIHZpc2libGUgZmllbGRzIGFmdGVyIGNvdmVyaW5nIHRoZSB0YWJsZSB3aXRoIGRvbWlub2VzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBmaXJzdCBleGFtcGxlOiBXZSBwbGFjZSB0aGUgZG9taW5vIHNvIGl0IGNvdmVycyBmaWVsZHMgd2l0aCBudW1iZXJzIDkgYW5kIDUuPFwvcD5cclxuXHJcbjxwPkNsYXJpZmljYXRpb24gb2YgdGhlIHNlY29uZCBleGFtcGxlOiBXZSBwbGFjZSB0aGUgZG9taW5vZXMgc28gdGhleSBjb3ZlciBmaWVsZHMgWzQsIDVdIGFuZCBbNSwgNF0gaW4gdGhlIHRoaXJkIGNvbHVtbi48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==