시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB1000.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

예제 입력 2

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

예제 출력 2

1
W3sicHJvYmxlbV9pZCI6IjI4MzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNDRcdWMyMGQgXHViMDk5XHVjMTFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MCBcdWI1NGMgXHVjODg1XHVjNzc0XHVjNWQwIFx1YjA5OVx1YzExY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1YjI5OFx1Yzc0MCAyJnRpbWVzO04gYnkgMiZ0aW1lcztOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWNjYjRcdWMyYTRcdWQzMTBcdWM3NDQgXHVhZGY4XHViODM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjNTQ0XHViNzk4IFx1YzEyNFx1YmE4NVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWMzNjggXHViMTkzXHViMjk0XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTg5XHVjNzU4IFx1YzkxMVx1YWMwNChOXHVjNWY0LCBOKzFcdWM1ZjQpXHVjNWQwIFx1YmU0NFx1YzIwZCBcdWI0NTAgXHVhYzFjXHViOTdjIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViZTQ0XHVjMjBkXHVjNzU4IFx1YzJkY1x1YzU3Y1x1Yjk3YyBcdWQ0NWNcdWMyZGNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmU0NFx1YzIwZFx1Yzc1OCBcdWMyZGNcdWM1N2NcdWI3ODAgXHViZTQ0XHVjMjBkXHVjNzc0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgTlx1Yzc3NCAzXHVjNzdjIFx1YjU0YywgXHViNDUwIFx1YmU0NFx1YzIwZFx1Yzc1OCBcdWMyZGNcdWM1N2NcdWIyOTQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1YmU0NFx1YzIwZFx1Yzc0MCBMXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWNlMCwgXHVjMmRjXHVjNTdjXHViMjk0IFhcdWI4NWMgXHVkNDVjXHVjMmRjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlxyXG5PT0xMT09cclxuT1hYWFhPXHJcblhYT09YWFxyXG5YT09PT1hcclxuT09PT09PXHJcbk9PT09PT1xyXG48XC9wcmU+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHViZTQ0XHVjMjBkXHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDY5Zlx1YzIxOFx1YjI5NCBcdWM4MWNcdWQ1NWNcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODA0XHViN2I1XHVjNzNjXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjNWJiXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJlNDRcdWMyMGRcdWM3NDQgXHVjNmMwXHVjOWMxXHVjNzc0XHVhZTMwIFx1YzgwNFx1YzVkMCwgXHViZTQ0XHVjMjBkXHVjNzU4IFx1YzJkY1x1YzU3Y1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWQ1NjlcdWM3NzQgXHVjZDA4XHVhZTMwIFx1YzgxMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1ZDEzNFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHViNTRjLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViNDUwIFx1YmU0NFx1YzIwZFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2UwXHViOTc0XHVhY2UwLCBcdWFkZjggXHVjMmRjXHVjNTdjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlNzggXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmU0NFx1YzIwZFx1Yzc0NCBcdWMwYzggXHVjNzA0XHVjZTU4XHViODVjIFx1Yzc3NFx1YjNkOVx1YzJkY1x1ZDBhNFx1YmE3NCwgXHVjNzc0XHVjODA0XHVjNWQwXHViMjk0IFx1YmNmYyBcdWMyMTggXHVjNWM2XHVjNWM4XHViMzU4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWNlNzhcdWM3NDQgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc5MCBcdWM3NzRcdWM4MWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCBcdWIyZTggXHVkNTVjIFx1YmM4OFx1YjNjNCBcdWJlNDRcdWMyMGRcdWM3NTggXHVjMmRjXHVjNTdjXHVjNWQwIFx1YjRlNFx1YzViNFx1YzYyOCBcdWM4MDFcdWM3NzQgXHVjNWM2XHVjOWMwXHViOWNjLCBcdWM3NzRcdWJjODggXHVjNzc0XHViM2Q5XHVjNzNjXHViODVjIFx1YzBjOFx1Yjg1Y1x1Yzc3NCBcdWJlNDRcdWMyMGRcdWM3NTggXHVjMmRjXHVjNTdjXHVjNWQwIFx1YjRlNFx1YzViNFx1YzYyOCBcdWNlNzhcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1ZDU2OVx1Yzc0NCBcdWM4MTBcdWMyMThcdWM1ZDAgXHVjZDk0XHVhYzAwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWQxMzRcdWM3NDQgS1x1YmM4OCBcdWMyMThcdWQ1ODlcdWQ1ODhcdWM3NDQgXHViNTRjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTlx1YWNmYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAsIDAgJmxlOyBLICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgMiZ0aW1lcztOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVkNTg5XHVjNWQwIFx1YzRmMFx1YzVlYyBcdWM3ODhcdWIyOTQgXHVjMjJiXHVjNzkwIDImdGltZXM7Tlx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWIyOTQgLTEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgzOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxPVkNJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBkcmV3IGEgMipOIGJ5IDIqTiBjaGVzc2JvYXJkIGFuZCBkZWNpZGVkIHRvIHBsYXkgdGhlIGZvbGxvd2luZyBnYW1lOjxcL3A+XHJcblxyXG48cD5PbiBlYWNoIHNxdWFyZSwgaGUgaW5zY3JpYmVkIGFuIGludGVnZXIgZGVub3RpbmcgdGhlIHZhbHVlIG9mIHRoYXQgc3F1YXJlLiBJbiB0aGUgbWlkZGxlIG9mIHRoZSBmaXJzdCByb3cgKGNvbHVtbnMgTiBhbmQgTisxKSwgaGUgcGxhY2VkIHR3byBiaXNob3BzLiBNaXJrbyBub3cgY2FsY3VsYXRlcyB0aGUgbGluZXMgb2Ygc2lnaHQgb2YgdGhlIHR3byBiaXNob3BzOiB0aGVzZSBhcmUgc3F1YXJlcyBvbiB0aGUgc2FtZSBkaWFnb25hbCBhcyBvbmUgb2YgdGhlIGJpc2hvcHMsIGJ1dCBub3Qgb24gdGhlIHNxdWFyZSBjb3ZlcmVkIGJ5IGFueSBvZiB0aGUgYmlzaG9wcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGluc3RhbmNlLCBpZiBOIGlzIDMsIHRoZSBzcXVhcmVzIHdpdGhpbiB0aGUgbGluZSBvZiBzaWdodCBvZiB0aGUgdHdvIGJpc2hvcHMgKGRlbm90ZWQgYnkgJiMzOTtYJiMzOTspIGF0IHRoZWlyIHN0YXJ0aW5nIHBvc2l0aW9ucyAoZGVub3RlZCBieSAmIzM5O0wmIzM5OykgYXJlIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjxwcmUgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHJcbk9PTExPT1xyXG5PWFhYWE9cclxuWFhPT1hYXHJcblhPT09PWFxyXG5PT09PT09cclxuT09PT09PXHJcbjxcL3ByZT5cclxuXHJcbjxwPkluIGEgbGltaXRlZCBudW1iZXIgb2YgbW92ZXMsIE1pcmtvIHRyaWVzIHRvIGdhaW4gdGhlIG1heGltdW0gc2NvcmUgYnkgdGhlIGZvbGxvd2luZyBzdHJhdGVneTombmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5CZWZvcmUgbWFraW5nIGFueSBtb3ZlcywgTWlya28gY2FsY3VsYXRlcyB0aGUgc3VtIG9mIHRoZSB2YWx1ZXMgb24gc3F1YXJlcyB3aXRoaW4gdGhlIGxpbmVzIG9mIHNpZ2h0Jm5ic3A7b2YgdGhlIHR3byBiaXNob3BzLiBUaGF0IGlzIE1pcmtvJiMzOTtzIGluaXRpYWwgc2NvcmUuJm5ic3A7PFwvbGk+XHJcblx0PGxpPk9uIGVhY2ggdHVybiwgTWlya28gY2hvb3NlcyBvbmUgb2YgdGhlIGJpc2hvcHMgYW5kIG1vdmVzIGl0IHRvIGEgc3F1YXJlIHdpdGhpbiBpdHMgbGluZSBvZiBzaWdodCZuYnNwOzxcL2xpPlxyXG5cdDxsaT5PbiBpdHMgbmV3IHBvc2l0aW9uLCB0aGUgYmlzaG9wIGNhbiBub3cgc2VlIG5ldyBzcXVhcmVzLiBUaGUgc3VtIG9mIHRob3NlIHNxdWFyZXMsIHByZXZpb3VzbHkgdW5zZWVuIGJ5IGFueSBvZiB0aGUgYmlzaG9wcyBmcm9tIHRoZSBzdGFydCBvZiB0aGUgZ2FtZSwgaXMgbm93IGFkZGVkIHRvIE1pcmtvJiMzOTtzIHNjb3JlLiZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBjYWxjdWxhdGVzIHRoZSBtYXhpbXVtIHNjb3JlIHRoYXQgTWlya28gY2FuIGFjaGlldmUgaW4gSyB0dXJucy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VyIE4gYW5kIEsgKDEgJmxlOyBOICZsZTsgMTAsIDAgJmxlOyBLICZsZTsgMTAwKSwgaGFsZiBvZiB0aGUgZGltZW5zaW9uIG9mIHRoZSBjaGVzc2JvYXJkIGFuZCB0aGUgbnVtYmVyIG9mIHR1cm5zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIDIqTiBsaW5lcyBjb250YWluIHRoZSB2YWx1ZXMgb2YgdGhlIHNxdWFyZXMgaW4gdGhlIGNvcnJlc3BvbmRpbmcgcm93LCAyKk4gdmFsdWVzIHBlciByb3cuIFRob3NlIHZhbHVlcyBhcmUgaW50ZWdlcnMgZnJvbSByYW5nZSAtMSAwMDAgMDAwIHRvIDEgMDAwIDAwMCwgaW5jbHVzaXZlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LCBwcmludCB0aGUgbWF4aW11bSBzY29yZSB0aGF0IE1pcmtvIGNhbiBhY2hpZXZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=