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

문제

상근이는 집 지하실에서 쥐를 발견했다. 쥐를 끔찍하게 싫어하는 상근이는 지하실에 쥐덫을 많이 설치했다.

지하실은 N*N 그리드로 나타낼 수 있다. 각 칸에는 해당 칸에 설치되어 있는 쥐덫의 개수가 저장되어 있다. 모든 칸에는 적어도 1개의 쥐덫이 있다.

신기하게도 정인이도 집 지하실에서 쥐를 발견했다. 하지만, 마을의 모든 쥐덫은 상근이가 모두 구매했기 때문에, 정인이는 살 수 있는 쥐덫이 없다. 어쩔수없이 정인이는 상근이에게 쥐덫을 빌려오려고 한다.

상근이와 정인이는 쥐덫에 대한 30분 동안 토론을 하였고, 상근이네 지하실의 쥐덫을 일부 제거해서 정인이에게 주기로 결정했다. 좀 더 자세하게 설명하자면 각각의 줄에 대해서, 연속된 K개의 칸을 선택한다. 그 뒤 선택한 칸에 있는 쥐덫을 모두 제거한 뒤 정인이에게 전달해 준다.

이렇게 쥐덫을 제거한 뒤에는 쥐는 상근이네 지하실의 왼쪽벽에서 오른쪽벽으로, 위쪽벽에서 아래쪽벽으로 지나갈 수 없어야 한다. 쥐는 4방향(위, 아래, 왼쪽, 오른쪽)으로 이동할 수 있고, 쥐덫이 하나도 없는 칸만 지나갈 수 있다.

위의 조건을 지키면서 상근이의 지하실에서 제거할 수 있는 쥐덫의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (2 ≤ N ≤ 250, 1 ≤ K ≤ N/2) N은 지하실의 크기, K는 각각의 줄에서 제거해야 하는 연속된 칸의 개수이다.

출력

첫째 줄에 상근이의 집에서 제거할 수 있는 쥐덫의 최대 개수를 출력한다.

예제 입력 1

4 2
5 5 1 1
1 5 5 1
1 1 5 5
5 5 1 1

예제 출력 1

36

힌트

W3sicHJvYmxlbV9pZCI6IjMxMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5NTBcdWIzNmIiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM5ZDEgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNWQwXHVjMTFjIFx1Yzk1MFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzk1MFx1Yjk3YyBcdWIwNTRcdWNjMGRcdWQ1NThcdWFjOGMgXHVjMmViXHVjNWI0XHVkNTU4XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM5YzBcdWQ1NThcdWMyZTRcdWM1ZDAgXHVjOTUwXHViMzZiXHVjNzQ0IFx1YjljZVx1Yzc3NCBcdWMxMjRcdWNlNThcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzljMFx1ZDU1OFx1YzJlNFx1Yzc0MCBOKk4gXHVhZGY4XHViOWFjXHViNGRjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNWQwXHViMjk0IFx1ZDU3NFx1YjJmOSBcdWNlNzhcdWM1ZDAgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWM5NTBcdWIzNmJcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IDFcdWFjMWNcdWM3NTggXHVjOTUwXHViMzZiXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMmUwXHVhZTMwXHVkNTU4XHVhYzhjXHViM2M0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjNjNCBcdWM5ZDEgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNWQwXHVjMTFjIFx1Yzk1MFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM5NTBcdWIzNmJcdWM3NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWI5ZTRcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMGI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOTUwXHViMzZiXHVjNzc0IFx1YzVjNlx1YjJlNC4gXHVjNWI0XHVjYTU0XHVjMjE4XHVjNWM2XHVjNzc0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjOTUwXHViMzZiXHVjNzQ0IFx1YmU0Y1x1YjgyNFx1YzYyNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjOTUwXHViMzZiXHVjNWQwIFx1YjMwMFx1ZDU1YyAzMFx1YmQ4NCBcdWIzZDlcdWM1NDggXHVkMWEwXHViODYwXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YzljMFx1ZDU1OFx1YzJlNFx1Yzc1OCBcdWM5NTBcdWIzNmJcdWM3NDQgXHVjNzdjXHViZDgwIFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzExYyBcdWM4MTVcdWM3NzhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjOGZjXHVhZTMwXHViODVjIFx1YWNiMFx1YzgxNVx1ZDU4OFx1YjJlNC4gXHVjODgwIFx1YjM1NCBcdWM3OTBcdWMxMzhcdWQ1NThcdWFjOGMgXHVjMTI0XHViYTg1XHVkNTU4XHVjNzkwXHViYTc0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM1ZjBcdWMxOGRcdWI0MWMgS1x1YWMxY1x1Yzc1OCBcdWNlNzhcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiBcdWFkZjggXHViNGE0IFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzk1MFx1YjM2Ylx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHVkNTVjIFx1YjRhNCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjODA0XHViMmVjXHVkNTc0IFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHViODA3XHVhYzhjIFx1Yzk1MFx1YjM2Ylx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NWMgXHViNGE0XHVjNWQwXHViMjk0IFx1Yzk1MFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHVjOWMwXHVkNTU4XHVjMmU0XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YmNiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWJjYmRcdWM3M2NcdWI4NWMsIFx1YzcwNFx1Y2FiZFx1YmNiZFx1YzVkMFx1YzExYyBcdWM1NDRcdWI3OThcdWNhYmRcdWJjYmRcdWM3M2NcdWI4NWMgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5NTBcdWIyOTQgNFx1YmMyOVx1ZDVhNShcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQpXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWM5NTBcdWIzNmJcdWM3NzQgXHVkNTU4XHViMDk4XHViM2M0IFx1YzVjNlx1YjI5NCBcdWNlNzhcdWI5Y2MgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM5YzBcdWQ1NThcdWMyZTRcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOTUwXHViMzZiXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDI1MCwgMSAmbGU7IEsgJmxlOyBOXC8yKSBOXHVjNzQwIFx1YzljMFx1ZDU1OFx1YzJlNFx1Yzc1OCBcdWQwNmNcdWFlMzAsIEtcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzkwNFx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWNlNzhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1YzVkMFx1YzExYyBcdWM4MWNcdWFjNzBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5NTBcdWIzNmJcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzExMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1JU09MT1ZLRSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIG1pY2UgaW4gTWlya28mIzM5O3MgYmFzZW1lbnQhIEFzIHNvb24gYXMgaGUgcmVhbGlzZWQsIGhlIGZpbGxlZCBoaXMgYmFzZW1lbnQgd2l0aCBtb3VzZXRyYXBzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IaXMgYmFzZW1lbnQgY2FuIGJlIG1vZGVsbGVkIGJ5IGFuIE4mdGltZXM7TiBncmlkLiBUaGVyZSBhcmUgYSBudW1iZXIgb2YgbW91c2V0cmFwcyBpbiBlYWNoIGNlbGwgYW5kIHRoaXMgbnVtYmVyIGlzIGtub3duIGZvciBlYWNoIGNlbGwuIFRoZXJlIGlzIGF0IGxlYXN0IG9uZSBtb3VzZXRyYXAgaW4gZXZlcnkgY2VsbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW1wcm9iYWJseSwgU2xhdmtvIGFsc28ganVzdCBkaXNjb3ZlcmVkIG1pY2UgaW4gaGlzIGJhc2VtZW50ISBIb3dldmVyLCBTbGF2a28gaGFzIG5vIG1vdXNldHJhcHMgc28gaGUgY2FtZSB0byBib3Jyb3cgc29tZSBmcm9tIE1pcmtvLiBCZWNhdXNlIE1pcmtvIGFscmVhZHkgbGFpZCBvdXQgaGlzIG1vdXNldHJhcHMgaW4gaGlzIGJhc2VtZW50IHRoZXkgbmVlZGVkIHRvIGZpZ3VyZSBvdXQgd2hhdCB0byBkby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhleSBkZWNpZGVkIHRvIHJlbW92ZSBzb21lIG1vdXNldHJhcHMgZnJvbSBNaXJrbyYjMzk7cyBiYXNlbWVudC4gTW9yZSBwcmVjaXNlbHksIGluIGVhY2ggcm93IHRoZXkgd2lsbCByZW1vdmUgYWxsIG1vdXNldHJhcHMgZnJvbSBleGFjdGx5IEsgY29uc2VjdXRpdmUgY2VsbHMuIEFmdGVyIGRvaW5nIHRoaXMgdGhlIG1pY2UgbXVzdCBub3QgYmUgYWJsZSB0byBjcm9zcyBmcm9tIHRoZSBsZWZ0IHRvIHRoZSByaWdodCBzaWRlIG9mIHRoZSBiYXNlbWVudCwgb3IgZnJvbSB0b3AgdG8gYm90dG9tLiBNaWNlIG1vdmUgaW4gdGhlIGZvdXIgY2FyZGluYWwgZGlyZWN0aW9ucyAodXAsIGRvd24sIGxlZnQgYW5kIHJpZ2h0KSBhbmQgY2FuIHBhc3Mgb25seSB0aHJvdWdoIGNlbGxzIHdpdGggbm8gbW91c2V0cmFwcyBpbiB0aGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5DYWxjdWxhdGUgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIG1vdXNldHJhcHMgdGhhdCBjYW4gYmUgcmVtb3ZlZCBmcm9tIE1pcmtvJiMzOTtzIGJhc2VtZW50LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBOICZsZTsgMjUwLCAxICZsZTsgSyAmbGU7IE5cLzIpLCB0aGUgZGltZW5zaW9uIG9mIHRoZSBiYXNlbWVudCBhbmQgdGhlIG51bWJlciBvZiBjb25zZWN1dGl2ZSBzcXVhcmVzIHRvIGJlIHJlbW92ZWQgZnJvbSBlYWNoIHJvdy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIG1vdXNldHJhcHMgdGhhdCBjYW4gYmUgcmVtb3ZlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d