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

문제

테트리스는 아래와 같은 5가지 조각으로 이루어져 있다.

정수로 이루어진 N×N 표가 주어진다. 테트리스 블럭 중 하나를 표에 놓아 블럭 아래에 있는 숫자의 합의 최대값을 구하는 프로그램을 작성하시오.

모든 테트리스 블럭은 90도씩 회전시킬 수 있다. 일부 조각은 총 4가지 형태를 가질 수 있다. 블럭이 모두 표 안에 들어있는 형태는 모두 가능한 형태이다.

예를 들어, 가장 왼쪽 블럭을 첫 행에 놓으면 합 80을 얻을 수 있다. 90도 회전시켜 셋째 열에 놓으면 91을 얻을 수 있다.

표의 크기가 4×4인 경우에 블럭을 놓는 방법의 수는 총 77가지이다. 위의 예제에서 가장 큰 합은 120이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 써 있는 숫자가 주어진다. 숫자는 절대값이 1,000,000을 넘지 않는 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스 마다, 케이스 번호를 출력하고 가장 큰 합을 출력한다.

예제 입력 1

4 
70  2  1 7
 7  1 30 6 
 4 30 30 5 
 3  1 30 2 
0

예제 출력 1

1. 120
W3sicHJvYmxlbV9pZCI6IjQ5MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCA1XHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RldC5wbmdcIiBzdHlsZT1cImhlaWdodDo1NnB4OyB3aWR0aDozNDNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IE4mdGltZXM7TiBcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWQyYjhcdWI5YWNcdWMyYTQgXHViZTE0XHViN2VkIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVkNDVjXHVjNWQwIFx1YjE5M1x1YzU0NCBcdWJlMTRcdWI3ZWQgXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDE0Y1x1ZDJiOFx1YjlhY1x1YzJhNCBcdWJlMTRcdWI3ZWRcdWM3NDAgOTBcdWIzYzRcdWM1MjkgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3Y1x1YmQ4MCBcdWM4NzBcdWFjMDFcdWM3NDAgXHVjZDFkIDRcdWFjMDBcdWM5YzAgXHVkNjE1XHVkMGRjXHViOTdjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJlMTRcdWI3ZWRcdWM3NzQgXHViYWE4XHViNDUwIFx1ZDQ1YyBcdWM1NDhcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1YjI5NCBcdWJhYThcdWI0NTAgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90ZXQyKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExNnB4OyB3aWR0aDo0NzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YmUxNFx1YjdlZFx1Yzc0NCBcdWNjYWIgXHVkNTg5XHVjNWQwIFx1YjE5M1x1YzczY1x1YmE3NCBcdWQ1NjkgODBcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIDkwXHViM2M0IFx1ZDY4Y1x1YzgwNFx1YzJkY1x1Y2YxYyBcdWMxNGJcdWM5ZjggXHVjNWY0XHVjNWQwIFx1YjE5M1x1YzczY1x1YmE3NCA5MVx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNDVjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCA0JnRpbWVzOzRcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YmUxNFx1YjdlZFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgNzdcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQ1NjlcdWM3NDAgMTIwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDQ1Y1x1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIDQgJmxlOyBOICZsZTsgMTAwXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWQ0NWNcdWM1ZDAgXHVjMzY4IFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjODA4XHViMzAwXHVhYzEyXHVjNzc0IDEsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCwgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiIgVGhlIEdhbWUgb2YgVGV0cmlzIiwiZGVzY3JpcHRpb24iOiI8cD5UZXRyaXMgaXMgYSBmYW1vdXMgdmlkZW8gZ2FtZSB0aGF0IGhhcyA1IHBpZWNlcyBzaW1pbGFyIHRvIHRoZXNlOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RldDMucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjQ3MnB4OyB3aWR0aDoxMjVweFwiIFwvPkluIHRoaXMgcHJvYmxlbSwgeW91JnJzcXVvO3JlIGdpdmVuIGFuIE54TiBncmlkIG9mIGludGVnZXJzLiBXZSB3YW50IHRvIHBsYWNlIGEgc2luZ2xlIHBpZWNlIG9mIFRldHJpcyBvbiB0aGUgZ3JpZCBzdWNoIHRoYXQgdGhlIHN1bSBvZiB0aGUgbnVtYmVycyBiZWxvdyB0aGUgcGllY2UgYXJlIHRoZSBtYXhpbXVtLiBOb3RpY2UgdGhhdCBhbGwgYnV0IHRoZSBsYXN0IFRldHJpcyBwaWVjZSBjYW4gYmUgcm90YXRlZCBieSA5MCBkZWdyZWVzLiBTb21lIHBpZWNlcyBldmVuIGhhdmUgZm91ciBkaVx1ZmIwMGVyZW50IG9yaWVudGF0aW9ucy4gQW55IG9yaWVudGF0aW9uIGlzIGFjY2VwdGFibGUgYXMgbG9uZyBhcyB0aGUgcGllY2UgY29tcGxldGVseSBcdWZiMDF0cyBpbnNpZGUgdGhlIGdyaWQuIEZvciBleGFtcGxlLCB0aGUgbGVmdC1tb3N0IHBpZWNlIGNhbiBiZSBwbGFjZWQgb24gdGhlIFx1ZmIwMXJzdCByb3cgb2YgdGhlIGdyaWQsIHdpdGggYSBzdW0gb2YgODAuIEl0IGNhbiBhbHNvIGJlIHBsYWNlZCwgZm9yIGV4YW1wbGUsIG9uIHRoZSB0aGlyZCBjb2x1bW4sIHlpZWxkaW5nIGEgc3VtIG9mIDkxLiBBcyBhIG1hdHRlciBvZiBmYWN0LCBpbiBhIDR4NCBncmlkLCB3ZSBjYW4gaGF2ZSA3NyBkaVx1ZmIwMGVyZW50IHdheXMgdG8gcGxhY2UgdGhlIFRldHJpcyBwaWVjZXMuIEluIHRoZSBzYW1wbGUgZ3JpZCBzaG93biBvbiB0aGUgcmlnaHQsIHRoZSBsYXJnZXN0IHN1bSB0aGF0IGNhbiBiZSBhY2hpZXZlZCBpcyAxMjAuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIGxhcmdlc3Qgc3VjaCBzdW0gZm9yIGEgZ2l2ZW4gZ3JpZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIHRlc3RlZCBvbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgaGFzIGEgc2luZ2xlIGludGVnZXIgTiBkZW5vdGluZyB0aGUgZ3JpZCBzaXplIHdoZXJlIDQgJmxlOyBOICZsZTsgMTAwLiBUaGUgZ3JpZCB3aWxsIGJlIHNwZWNpXHVmYjAxZWQgdXNpbmcgTiBsaW5lcyBzdGFydGluZyBvbiB0aGUgc2Vjb25kIGxpbmUgaW4gYSByb3cgbWFqb3IgZm9ybWF0LiBFYWNoIGxpbmUgd2lsbCBoYXZlIE4gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IG9uZSBvciBtb3JlIHNwYWNlcy4gVGhlIGFic29sdXRlIHZhbHVlIG9mIGVhY2ggaW50ZWdlciBpbiB0aGUgZ3JpZCB3aWxsIG5vdCBleGNlZWQgMSwwMDAsMDAwLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBjYXNlcyBpcyBzcGVjaVx1ZmIwMWVkIGJ5IGEgemVybyBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIHJlc3VsdCBvbiBhIHNpbmdsZSBsaW5lIHVzaW5nIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48cHJlPlxyXG5rLnJlc3VsdDxcL3ByZT5cclxuXHJcbjxwPldoZXJlIGsgaXMgdGhlIHRlc3QgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGF0IDEsKSBhbmQgcmVzdWx0IGlzIHRoZSBsYXJnZXN0IHN1bSB0aGF0IGNhbiBiZSBvYnRhaW5lZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=