(追記) (追記ここまで)

31725번 - 포닉스와 달구 다국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1.5 초	1024 MB	113	56	47	48.958%

문제

포닉스와 달구는 $N \times N$ 크기의 격자 위에서 놀이를 하려고 한다. 이 격자의 $i$행 $j$열에 위치한 칸에는 가중치 $A_{i, j}$가 있다. 놀이의 방법은 아래와 같다.

달구는 $K \times K$ 크기의 영역을 하나 골라서, 해당 영역의 칸들을 윤이에게 선물로 준다. 단, 달구가 선물할 영역에는 격자의 1ドル$행 1ドル$열과 $N$행 $N$열이 포함되면 안 된다.
포닉스는 처음에 격자의 1ドル$행 1ドル$열에 있고, $N$행 $N$열에 도달할 때까지 이동한다. 포닉스는 현재 위치한 칸이 $r$행 $c$열일 때, $r+1$행 $c$열 또는 $r$행 $c+1$열로 이동할 수 있다. 단, 격자 밖이나 윤이가 선물받은 칸으로는 이동할 수 없다.
포닉스가 얻을 수 있는 점수는 포닉스가 지나간 칸에 포함된 가중치의 합이다.

포닉스는 점수를 최대로 얻고자 하고, 달구는 포닉스의 점수가 최소가 되도록 영역을 고르고자 한다. 포닉스와 달구는 모두 최선을 다해 놀이를 진행한다고 가정했을 때, 포닉스가 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 격자의 크기 $N$과 $K$가 공백으로 구분되어 주어진다. $(2 \le N \le 2\ 000; 1 \le K < N)$

다음 $N$개의 줄에는 $N$개의 정수 $A_{i, 1}, A_{i, 2}, \cdots, A_{i, N}$이 공백으로 구분되어 주어진다. $(0 \le A_{i, j} \le 10\ 000)$

출력

포닉스가 얻을 수 있는 점수의 최댓값을 출력한다.

제한

예제 입력 1

5 3
4 8 13 2 5
0 7 7 3 12
25 3 11 5 6
9 12 0 28 3
1 13 5 8 9

예제 출력 1

힌트

W3sicHJvYmxlbV9pZCI6IjMxNzI1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkM2VjXHViMmM5XHVjMmE0XHVjNjQwIFx1YjJlY1x1YWQ2YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVkM2VjXHViMmM5XHVjMmE0XHVjNjQwIFx1YjJlY1x1YWQ2Y1x1YjI5NCAkTiBcXHRpbWVzIE4kIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjYTlcdWM3OTAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhY2E5XHVjNzkwXHVjNzU4ICRpJFx1ZDU4OSAkaiRcdWM1ZjRcdWM1ZDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM5MTFcdWNlNTggJEFfe2ksIGp9JFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjE4MFx1Yzc3NFx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48c3Ryb25nPlx1YjJlY1x1YWQ2YzxcL3N0cm9uZz5cdWIyOTQgJEsgXFx0aW1lcyBLJCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjNjAxXHVjNWVkXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWFjZThcdWI3N2NcdWMxMWMsIFx1ZDU3NFx1YjJmOSBcdWM2MDFcdWM1ZWRcdWM3NTggXHVjZTc4XHViNGU0XHVjNzQ0IDxzdHJvbmc+XHVjNzI0XHVjNzc0PFwvc3Ryb25nPlx1YzVkMFx1YWM4YyBcdWMxMjBcdWJiM2NcdWI4NWMgXHVjOTAwXHViMmU0LiBcdWIyZTgsIFx1YjJlY1x1YWQ2Y1x1YWMwMCBcdWMxMjBcdWJiM2NcdWQ1NjAgXHVjNjAxXHVjNWVkXHVjNWQwXHViMjk0IFx1YWNhOVx1Yzc5MFx1Yzc1OCAkMSRcdWQ1ODkgJDEkXHVjNWY0XHVhY2ZjICROJFx1ZDU4OSAkTiRcdWM1ZjRcdWM3NzQgXHVkM2VjXHVkNTY4XHViNDE4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+XHVkM2VjXHViMmM5XHVjMmE0PFwvc3Ryb25nPlx1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgXHVhY2E5XHVjNzkwXHVjNzU4ICQxJFx1ZDU4OSAkMSRcdWM1ZjRcdWM1ZDAgXHVjNzg4XHVhY2UwLCAkTiRcdWQ1ODkgJE4kXHVjNWY0XHVjNWQwIFx1YjNjNFx1YjJlY1x1ZDU2MCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWQzZWNcdWIyYzlcdWMyYTRcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YzcwNFx1Y2U1OFx1ZDU1YyBcdWNlNzhcdWM3NzQgJHIkXHVkNTg5ICRjJFx1YzVmNFx1Yzc3YyBcdWI1NGMsICRyKzEkXHVkNTg5ICRjJFx1YzVmNCBcdWI2MTBcdWIyOTQgJHIkXHVkNTg5ICRjKzEkXHVjNWY0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YWNhOVx1Yzc5MCBcdWJjMTZcdWM3NzRcdWIwOTggXHVjNzI0XHVjNzc0XHVhYzAwIFx1YzEyMFx1YmIzY1x1YmMxYlx1Yzc0MCBcdWNlNzhcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1ZDNlY1x1YjJjOVx1YzJhNFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCA8c3Ryb25nPlx1YzgxMFx1YzIxODxcL3N0cm9uZz5cdWIyOTQgXHVkM2VjXHViMmM5XHVjMmE0XHVhYzAwIFx1YzljMFx1YjA5OFx1YWMwNCBcdWNlNzhcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkM2VjXHViMmM5XHVjMmE0XHViMjk0IFx1YzgxMFx1YzIxOFx1Yjk3YyA8c3Ryb25nPlx1Y2Q1Y1x1YjMwMDxcL3N0cm9uZz5cdWI4NWMgXHVjNWJiXHVhY2UwXHVjNzkwIFx1ZDU1OFx1YWNlMCwgXHViMmVjXHVhZDZjXHViMjk0IFx1ZDNlY1x1YjJjOVx1YzJhNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWFjMDAgPHN0cm9uZz5cdWNkNWNcdWMxOGM8XC9zdHJvbmc+XHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVhY2UwXHViOTc0XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVkM2VjXHViMmM5XHVjMmE0XHVjNjQwIFx1YjJlY1x1YWQ2Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHVjZDVjXHVjMTIwXHVjNzQ0IFx1YjJlNFx1ZDU3NCBcdWIxODBcdWM3NzRcdWI5N2MgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1ZDNlY1x1YjJjOVx1YzJhNFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2E5XHVjNzkwXHVjNzU4IFx1ZDA2Y1x1YWUzMCAkTiRcdWFjZmMgJEskXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDIgXFxsZSBOIFxcbGUgMlxcIDAwMDsgMSBcXGxlIEsgJmx0OyBOKSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQV97aSwgMX0sIEFfe2ksIDJ9LCBcXGNkb3RzLCBBX3tpLCBOfSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMCBcXGxlIEFfe2ksIGp9IFxcbGUgMTBcXCAwMDApJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDNlY1x1YjJjOVx1YzJhNFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTcyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvbml4IGFuZCBEYWxnb28iLCJkZXNjcmlwdGlvbiI6IjxwPlBvbml4IGFuZCBEYWxnb28gd2FudCB0byBwbGF5IGEgZ2FtZSBvbiBhIGdyaWQgb2Ygc2l6ZSAkTiBcXHRpbWVzIE4kLiBFYWNoIGNlbGwgaW4gdGhpcyBncmlkLCBsb2NhdGVkIGF0IHJvdyAkaSQgYW5kIGNvbHVtbiAkaiQsIGNvbnRhaW5zIGEgd2VpZ2h0ICRBX3tpLCBqfSQuIFRoZSBydWxlcyBvZiB0aGUgZ2FtZSBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48c3Ryb25nPkRhbGdvbzxcL3N0cm9uZz4gc2VsZWN0cyBvbmUgYXJlYSBvZiBzaXplICRLIFxcdGltZXMgSyQgYW5kIGdpdmVzIHRoZSBjZWxscyB3aXRoaW4gdGhhdCBhcmVhIGFzIGEgZ2lmdCB0byA8c3Ryb25nPll1bmVlPFwvc3Ryb25nPi4gSG93ZXZlciwgRGFsZ29vIG11c3QgZW5zdXJlIHRoYXQgdGhlIHNlbGVjdGVkIGFyZWEgZm9yIHRoZSBnaWZ0IGRvZXMgbm90IGluY2x1ZGUgdGhlIGNlbGwmbmJzcDthdCB0aGUgZmlyc3Qgcm93IGFuZCBmaXJzdCBjb2x1bW4sIG5vciB0aGUgY2VsbCZuYnNwO2F0IHRoZSAkTiQtdGggcm93IGFuZCAkTiQtdGggY29sdW1uIG9mIHRoZSBncmlkLjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlBvbml4PFwvc3Ryb25nPiBzdGFydHMgYXQgdGhlIGNlbGwgbG9jYXRlZCBhdCB0aGUgZmlyc3Qgcm93IGFuZCBmaXJzdCBjb2x1bW4gb2YgdGhlIGdyaWQgYW5kIG1vdmVzIHVudGlsIHJlYWNoaW5nIHRoZSBjZWxsIGF0IHRoZSAkTiQtdGggcm93IGFuZCAkTiQtdGggY29sdW1uLiBQb25peCBjYW4gbW92ZSBlaXRoZXIgdG8gdGhlIGNlbGwgYmVsb3cgb3IgdG8gdGhlIGNlbGwgdG8gdGhlIHJpZ2h0IG9mIHRoZWlyIGN1cnJlbnQgcG9zaXRpb24uIEhvd2V2ZXIsIFBvbml4IGNhbm5vdCBtb3ZlIG91dHNpZGUgdGhlIGdyaWQgb3IgdG8gdGhlIGNlbGxzIHRoYXQgWXVuZWUgcmVjZWl2ZWQgYXMgZ2lmdHMuPFwvbGk+XHJcblx0PGxpPlRoZSA8c3Ryb25nPnNjb3JlPFwvc3Ryb25nPiBQb25peCBjYW4gb2J0YWluIGlzIHRoZSBzdW0gb2YgdGhlIHdlaWdodHMgb2YgdGhlIGNlbGxzIHZpc2l0ZWQgYnkgUG9uaXggZHVyaW5nIHRoZWlyJm5ic3A7bW92ZW1lbnQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UG9uaXggd2FudHMgdG8gPHN0cm9uZz5tYXhpbWl6ZTxcL3N0cm9uZz4gdGhlIHNjb3JlLCB3aGlsZSBEYWxnb28gd2FudHMgdG8gPHN0cm9uZz5taW5pbWl6ZTxcL3N0cm9uZz4gUG9uaXgmIzM5O3Mgc2NvcmUgYnkgc3RyYXRlZ2ljYWxseSBzZWxlY3RpbmcgdGhlIGFyZWEgZm9yIHRoZSBnaWZ0LiBBc3N1bWluZyBib3RoIFBvbml4IGFuZCBEYWxnb28gcGxheSBvcHRpbWFsbHksJm5ic3A7ZmluZCB0aGUgbWF4aW11bSBzY29yZSBQb25peCBjYW4gb2J0YWluLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciAkTiQgcmVwcmVzZW50aW5nIHRoZSBzaXplIG9mIHRoZSBncmlkIGFuZCAkSyQuICQoMiBcXGxlIE4gXFxsZSAyXFwgMDAwOyAxIFxcbGUgSyAmbHQ7IE4pJDxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJE4kIGxpbmVzIG9mIGlucHV0IGNvbnRhaW5zICROJCZuYnNwO3NwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyZuYnNwOyRBX3tpLCAxfSwgQV97aSwgMn0sIFxcY2RvdHMsIEFfe2ksIE59JC4mbmJzcDskKDAgXFxsZSBBX3tpLCBqfSBcXGxlIDEwXFwgMDAwKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1heGltdW0gc2NvcmUgdGhhdCBQb25peCBjYW4gYWNoaWV2ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d