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

문제

선영이는 문제를 풀 때 종이에 낙서를 한다. 오늘은 2×N by 2×N 크기의 체스판을 그렸다.

오늘은 아래 설명과 같은 게임을 할 것이다.

먼저 각 칸에 정수를 써 놓는다. 먼저, 첫 번째 행의 중간(N열, N+1열)에 비숍 두 개를 놓는다. 그 다음에 선영이는 비숍의 시야를 표시한다.

비숍의 시야란 비숍이 이동할 수 있는 칸이다.

예를 들어, N이 3일 때, 두 비숍의 시야는 아래 그림과 같다. 비숍은 L로 표시하고, 시야는 X로 표시한다.

OOLLOO
OXXXXO
XXOOXX
XOOOOX
OOOOOO
OOOOOO

선영이가 비숍을 움직일 수 있는 횟수는 제한이 있다. 따라서, 아래와 같은 전략으로 최대 점수를 얻으려고 한다.

1. 비숍을 움직이기 전에, 비숍의 시야에 들어있는 칸에 써 있는 숫자의 합을 계산한다. 이 합이 초기 점수이다.

2. 각 턴을 수행할 때, 선영이는 두 비숍중 하나를 고르고, 그 시야에 있는 칸 중 하나로 이동한다.

3. 비숍을 새 위치로 이동시키면, 이전에는 볼 수 없었던 새로운 칸을 볼 수 있다. 자 이제 게임을 시작하고 단 한 번도 비숍의 시야에 들어온 적이 없지만, 이번 이동으로 새로이 비숍의 시야에 들어온 칸에 써 있는 숫자의 합을 구한다. 이 합을 점수에 추가한다.

선영이가 턴을 K번 수행했을 때 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ 100)

다음 2×N개 줄에는 해당하는 행에 써 있는 숫자 2×N개가 주어진다. 각 숫자는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 선영이가 얻을 수 있는 최대 점수를 출력한다.

예제 입력 1

2 0
0 -9 -9 0
0 1 1 0
1 0 0 1
0 0 6 0

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI4MzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWMyMGQgXHViMDk5XHVjMTFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWI1NGMgXHVjODg1XHVjNzc0XHVjNWQwIFx1YjA5OVx1YzExY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1YjI5OFx1Yzc0MCAyJnRpbWVzO04gYnkgMiZ0aW1lcztOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NDQgXHVhZGY4XHViODM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjNTQ0XHViNzk4IFx1YzEyNFx1YmE4NVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWMzNjggXHViMTkzXHViMjk0XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTg5XHVjNzU4IFx1YzkxMVx1YWMwNChOXHVjNWY0LCBOKzFcdWM1ZjQpXHVjNWQwIFx1YmU0NFx1YzIwZCBcdWI0NTAgXHVhYzFjXHViOTdjIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViZTQ0XHVjMjBkXHVjNzU4IFx1YzJkY1x1YzU3Y1x1Yjk3YyBcdWQ0NWNcdWMyZGNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmU0NFx1YzIwZFx1Yzc1OCBcdWMyZGNcdWM1N2NcdWI3ODAgXHViZTQ0XHVjMjBkXHVjNzc0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTlx1Yzc3NCAzXHVjNzdjIFx1YjU0YywgXHViNDUwIFx1YmU0NFx1YzIwZFx1Yzc1OCBcdWMyZGNcdWM1N2NcdWIyOTQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1YmU0NFx1YzIwZFx1Yzc0MCBMXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWNlMCwgXHVjMmRjXHVjNTdjXHViMjk0IFhcdWI4NWMgXHVkNDVjXHVjMmRjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5PT0xMT09cclxuT1hYWFhPXHJcblhYT09YWFxyXG5YT09PT1hcclxuT09PT09PXHJcbk9PT09PT1xyXG48XC9wcmU+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViZTQ0XHVjMjBkXHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDY5Zlx1YzIxOFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODA0XHViN2I1XHVjNzNjXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MS4gXHViZTQ0XHVjMjBkXHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YWUzMCBcdWM4MDRcdWM1ZDAsIFx1YmU0NFx1YzIwZFx1Yzc1OCBcdWMyZGNcdWM1N2NcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1Y2U3OFx1YzVkMCBcdWMzNjggXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVkNTY5XHVjNzc0IFx1Y2QwOFx1YWUzMCBcdWM4MTBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjIuIFx1YWMwMSBcdWQxMzRcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTYwIFx1YjU0YywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWJlNDRcdWMyMGRcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlMFx1Yjk3NFx1YWNlMCwgXHVhZGY4IFx1YzJkY1x1YzU3Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTc4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4zLiBcdWJlNDRcdWMyMGRcdWM3NDQgXHVjMGM4IFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYTRcdWJhNzQsIFx1Yzc3NFx1YzgwNFx1YzVkMFx1YjI5NCBcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YzVjOFx1YjM1OCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjZTc4XHVjNzQ0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3OTAgXHVjNzc0XHVjODFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAgXHViMmU4IFx1ZDU1YyBcdWJjODhcdWIzYzQgXHViZTQ0XHVjMjBkXHVjNzU4IFx1YzJkY1x1YzU3Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWM2MjggXHVjODAxXHVjNzc0IFx1YzVjNlx1YzljMFx1YjljYywgXHVjNzc0XHViYzg4IFx1Yzc3NFx1YjNkOVx1YzczY1x1Yjg1YyBcdWMwYzhcdWI4NWNcdWM3NzQgXHViZTQ0XHVjMjBkXHVjNzU4IFx1YzJkY1x1YzU3Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWM2MjggXHVjZTc4XHVjNWQwIFx1YzM2OCBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWQ1NjlcdWM3NDQgXHVjODEwXHVjMjE4XHVjNWQwIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1ZDEzNFx1Yzc0NCBLXHViYzg4IFx1YzIxOFx1ZDU4OVx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMCwgMCAmbGU7IEsgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAyJnRpbWVzO05cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1ODlcdWM1ZDAgXHVjMzY4IFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTAgMiZ0aW1lcztOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YjI5NCAtMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTE9WQ0kiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGRyZXcgYSAyKk4gYnkgMipOIGNoZXNzYm9hcmQgYW5kIGRlY2lkZWQgdG8gcGxheSB0aGUgZm9sbG93aW5nIGdhbWU6PFwvcD5cclxuXHJcbjxwPk9uIGVhY2ggc3F1YXJlLCBoZSBpbnNjcmliZWQgYW4gaW50ZWdlciBkZW5vdGluZyB0aGUgdmFsdWUgb2YgdGhhdCBzcXVhcmUuIEluIHRoZSBtaWRkbGUgb2YgdGhlIGZpcnN0IHJvdyAoY29sdW1ucyBOIGFuZCBOKzEpLCBoZSBwbGFjZWQgdHdvIGJpc2hvcHMuIE1pcmtvIG5vdyBjYWxjdWxhdGVzIHRoZSBsaW5lcyBvZiBzaWdodCBvZiB0aGUgdHdvIGJpc2hvcHM6IHRoZXNlIGFyZSBzcXVhcmVzIG9uIHRoZSBzYW1lIGRpYWdvbmFsIGFzIG9uZSBvZiB0aGUgYmlzaG9wcywgYnV0IG5vdCBvbiB0aGUgc3F1YXJlIGNvdmVyZWQgYnkgYW55IG9mIHRoZSBiaXNob3BzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgaW5zdGFuY2UsIGlmIE4gaXMgMywgdGhlIHNxdWFyZXMgd2l0aGluIHRoZSBsaW5lIG9mIHNpZ2h0IG9mIHRoZSB0d28gYmlzaG9wcyAoZGVub3RlZCBieSAmIzM5O1gmIzM5OykgYXQgdGhlaXIgc3RhcnRpbmcgcG9zaXRpb25zIChkZW5vdGVkIGJ5ICYjMzk7TCYjMzk7KSBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHByZT5cclxuT09MTE9PXHJcbk9YWFhYT1xyXG5YWE9PWFhcclxuWE9PT09YXHJcbk9PT09PT1xyXG5PT09PT09cclxuPFwvcHJlPlxyXG5cclxuPHA+SW4gYSBsaW1pdGVkIG51bWJlciBvZiBtb3ZlcywgTWlya28gdHJpZXMgdG8gZ2FpbiB0aGUgbWF4aW11bSBzY29yZSBieSB0aGUgZm9sbG93aW5nIHN0cmF0ZWd5OiZuYnNwOzxcL3A+XHJcblxyXG48cD4xLiBCZWZvcmUgbWFraW5nIGFueSBtb3ZlcywgTWlya28gY2FsY3VsYXRlcyB0aGUgc3VtIG9mIHRoZSB2YWx1ZXMgb24gc3F1YXJlcyB3aXRoaW4gdGhlIGxpbmVzIG9mIHNpZ2h0Jm5ic3A7PFwvcD5cclxuXHJcbjxwPm9mIHRoZSB0d28gYmlzaG9wcy4gVGhhdCBpcyBNaXJrbyYjMzk7cyBpbml0aWFsIHNjb3JlLiZuYnNwOzxcL3A+XHJcblxyXG48cD4yLiBPbiBlYWNoIHR1cm4sIE1pcmtvIGNob29zZXMgb25lIG9mIHRoZSBiaXNob3BzIGFuZCBtb3ZlcyBpdCB0byBhIHNxdWFyZSB3aXRoaW4gaXRzIGxpbmUgb2Ygc2lnaHQmbmJzcDs8XC9wPlxyXG5cclxuPHA+My4gT24gaXRzIG5ldyBwb3NpdGlvbiwgdGhlIGJpc2hvcCBjYW4gbm93IHNlZSBuZXcgc3F1YXJlcy4gVGhlIHN1bSBvZiB0aG9zZSBzcXVhcmVzLCBwcmV2aW91c2x5IHVuc2VlbiBieSBhbnkgb2YgdGhlIGJpc2hvcHMgZnJvbSB0aGUgc3RhcnQgb2YgdGhlIGdhbWUsIGlzIG5vdyBhZGRlZCB0byBNaXJrbyYjMzk7cyBzY29yZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGNhbGN1bGF0ZXMgdGhlIG1heGltdW0gc2NvcmUgdGhhdCBNaXJrbyBjYW4gYWNoaWV2ZSBpbiBLIHR1cm5zLiZuYnNwOzxcL3A+IiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlciBOIGFuZCBLICgxICZsZTsgTiAmbGU7IDEwLCAwICZsZTsgSyAmbGU7IDEwMCksIGhhbGYgb2YgdGhlIGRpbWVuc2lvbiBvZiB0aGUgY2hlc3Nib2FyZCBhbmQgdGhlIG51bWJlciBvZiB0dXJucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyAyKk4gbGluZXMgY29udGFpbiB0aGUgdmFsdWVzIG9mIHRoZSBzcXVhcmVzIGluIHRoZSBjb3JyZXNwb25kaW5nIHJvdywgMipOIHZhbHVlcyBwZXIgcm93LiBUaG9zZSB2YWx1ZXMgYXJlIGludGVnZXJzIGZyb20gcmFuZ2UgLTEgMDAwIDAwMCB0byAxIDAwMCAwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiBhIHNpbmdsZSBsaW5lIG9mIG91dHB1dCwgcHJpbnQgdGhlIG1heGltdW0gc2NvcmUgdGhhdCBNaXJrbyBjYW4gYWNoaWV2ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=