시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWIwYThcdWM2YjFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYyZuYnNwO1x1YmNmNFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2M0XHViNzgwXHVjNzU4IFx1YzM2OVx1Yzc0Y1x1YjNjNCBcdWQ1NjlcdWM3NDQgXHVjNWJjXHViOWNjXHVkMDdjIFx1YjBhZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YjgyNFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjYzRcdWI3ODBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIE4gKDEgJmxlOyBOICZsZTsgMiwwMDApXHVjNjQwIFx1YWMwMFx1YjliY1x1ZDMxMFx1Yzc1OCBcdWFjMWNcdWMyMTggSyZuYnNwOygxICZsZTsgSyAmbGU7IDgpIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjQ1OFx1YzlmOFx1YzkwNCBcdWJkODBcdWQxMzAgTiArIDFcdWM5MDRcdWFlNGNcdWM5YzAgXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBOXHVhYzFjXHVjNzU4IFx1YWMwMSBcdWFjYzRcdWI3ODBcdWM3NTgmbmJzcDtcdWMzNjlcdWM3NGNcdWIzYzQgRiAoIDAgJmxlOyBGICZsZTsgMSwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjhcdWM5MDRcdWM1ZDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWJjZjRcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YWNjNFx1Yjc4MFx1Yzc1OCBcdWMzNjlcdWM3NGNcdWIzYzQgXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWM6Jm5ic3A7PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YWMwMFx1YjliY1x1ZDMxMFx1Yzc0NCBcdWMzNjlcdWM3NGNcdWIzYzQgOVx1YzY0MCA1XHVjNzA0XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC48XC9zcGFuPjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjOiZuYnNwOzxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFjMDBcdWI5YmNcdWQzMTBcdWM3NDQgWzQsIDVdXHVjNjQwIFs1LCA0XVx1YzVkMCBcdWIxOTNcdWIyOTRcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNzc3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRE9NSU5PIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyByZWNlaXZlZCBhbiBOICZ0aW1lczsgTiB0YWJsZSBmb3IgaGlzIGJpcnRoZGF5LCB3aGVyZSBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIGlzIHdyaXR0ZW4gaW4gZWFjaCBmaWVsZCBvZiB0aGUgdGFibGUuIFVuZm9ydHVuYXRlbHksIHRoZSB3cml0dGVuIG51bWJlcnMgYXJlIHRvbyBsYXJnZSBmb3IgTWlya28mcnNxdW87cyB0YXN0ZSwgc28gaGUgd2lsbCBwbGFjZSBLIGRvbWlub2VzIG9uIHRvcCBvZiB0aGUgdGFibGUgdGhhdCB3aWxsIGNvdmVyIHRoZSBmaWVsZHMgdGhhdCBhcmUgdG9vIGxhcmdlLjxcL3A+XHJcblxyXG48cD5Nb3JlIHByZWNpc2VseSwgTWlya28gcGxhY2VzIHRoZSBkb21pbm9lcyBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5lYWNoIGRvbWlubyBjb3ZlcnMgdHdvIGZpZWxkcyBvZiB0aGUgdGFibGUgdGhhdCBhcmUgYWRqYWNlbnQgaW4gYSByb3cgb3IgaW4gYSBjb2x1bW4sPFwvbGk+XHJcblx0PGxpPnRoZSBkb21pbm9lcyBkbyBub3Qgb3ZlcmxhcCAoYnV0IGNhbiB0b3VjaCksPFwvbGk+XHJcblx0PGxpPnRoZSBzdW0gb2YgYWxsIHZpc2libGUgKHVuY292ZXJlZCkgZmllbGRzIG5lZWRzIHRvIGJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkl0IGlzIHlvdXIgdGFzayB0byBkZXRlcm1pbmUgdGhlIHJlcXVpcmVkIG1pbmltYWwgc3VtIG9mIHZpc2libGUgZmllbGRzLiBUaGUgdGVzdCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IGl0IHdpbGwgYWx3YXlzIGJlIHBvc3NpYmxlIHRvIHBsYWNlIEsgZG9taW5vZXMgd2l0aG91dCBvdmVybGFwcGluZy4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlcnMgTiAoMSAmbGU7IE4gJmxlOyAyMDAwKSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHRhYmxlLCBhbmQgSyAoMSAmbGU7IEsgJmxlOyA4KSwgdGhlIG51bWJlciBvZiBkb21pbm9lcy4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgTiBpbnRlZ2VycyBmcm9tIHRoZSBpbnRlcnZhbCBbMCwgMTAwMF0uIFRoZXNlIE4gJnRpbWVzOyBOIG51bWJlcnMgZGVzY3JpYmUgTWlya28mcnNxdW87cyB0YWJsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbWFsIHN1bSBvZiB2aXNpYmxlIGZpZWxkcyBhZnRlciBjb3ZlcmluZyB0aGUgdGFibGUgd2l0aCBkb21pbm9lcy48XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogV2UgcGxhY2UgdGhlIGRvbWlubyBzbyBpdCBjb3ZlcnMgZmllbGRzIHdpdGggbnVtYmVycyA5IGFuZCA1LjxcL3A+XHJcblxyXG48cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBzZWNvbmQgZXhhbXBsZTogV2UgcGxhY2UgdGhlIGRvbWlub2VzIHNvIHRoZXkgY292ZXIgZmllbGRzIFs0LCA1XSBhbmQgWzUsIDRdIGluIHRoZSB0aGlyZCBjb2x1bW4uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=