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

문제

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.

오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야할지를 아직 결정을 하지 못했다.

수석코치 마이크 펠란은 11명 선수가 각각의 포지션에서의 능력을 0부터 100가지의 숫자로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.

이때, 모든 선수의 포지션을 정해지는 프로그램을 작성하시오. 모든 포지션에 해당하는 선수가 있어야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100사이의 11개의 정수 sij를 포함하고 있다. sij는 i번선수가 j번 포지션에서 뛸 때의 능력이다. 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)

출력

각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 1개의 올바른 라인업을 만들 수 있다.

예제 입력 1

1
100 0 0 0 0 0 0 0 0 0 0
0 80 70 70 60 0 0 0 0 0 0
0 40 90 90 40 0 0 0 0 0 0
0 40 85 85 33 0 0 0 0 0 0
0 70 60 60 85 0 0 0 0 0 0
0 0 0 0 0 95 70 60 60 0 0
0 45 0 0 0 80 90 50 70 0 0
0 0 0 0 0 40 90 90 40 70 0
0 0 0 0 0 0 50 70 85 50 0
0 0 0 0 0 0 66 60 0 80 80
0 0 0 0 0 0 50 50 0 90 88

예제 출력 1

970
W3sicHJvYmxlbV9pZCI6IjM5ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMjBcdWJjMWMgXHViYTg1XHViMmU4IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWNjNTRcdWQ1M2NcdWM1YjhcdWMyYTQgXHViOWFjXHVhZGY4IFx1YWNiMFx1YzJiOVx1YzgwNFx1Yzc0NCBcdWM1NWVcdWI0NTBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjllOFx1Y2NiNFx1YzJhNFx1ZDEzMCBcdWM3MjBcdWIwOThcdWM3NzRcdWQyZjBcdWI0ZGNcdWM3NTggXHViYTg1XHVjN2E1IFx1ZDM3Y1x1YWM3MFx1YzJhOCBcdWFjMTBcdWIzYzVcdWM3NDAgXHVjNzc0XHViYzg4IFx1YWNiZFx1YWUzMFx1YzVkMCA0LTQtMiBcdWIyZTRcdWM3NzRcdWM1NDRcdWJhYWNcdWI0ZGMgXHVjODA0XHVjMjIwXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC80NDIucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTcwcHg7IGhlaWdodDogMjI2cHg7IGZsb2F0OiByaWdodDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjI0XHViMjk4IFx1YWNiMFx1YzJiOVx1YzgwNFx1YzVkMCBcdWI2ZjggXHVjMTIwXHViYzFjIFx1YzEyMFx1YzIxOCAxMVx1YmE4NVx1Yzc0MCBcdWJiZjhcdWI5YWMgXHVhY2U4XHViNzdjXHViNDUwXHVjNWM4XHVjOWMwXHViOWNjLCBcdWM1YjRcdWI1YTQgXHVjMTIwXHVjMjE4XHViOTdjIFx1YzViNFx1YjI5MCBcdWQzZWNcdWM5YzBcdWMxNThcdWM1ZDAgXHViYzMwXHVjZTU4XHVkNTc0XHVjNTdjXHVkNTYwXHVjOWMwXHViOTdjIFx1YzU0NFx1YzljMSBcdWFjYjBcdWM4MTVcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMjE4XHVjMTFkXHVjZjU0XHVjZTU4IFx1YjljOFx1Yzc3NFx1ZDA2YyBcdWQzYTBcdWI3ODBcdWM3NDAgMTFcdWJhODUgXHVjMTIwXHVjMjE4XHVhYzAwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQzZWNcdWM5YzBcdWMxNThcdWM1ZDBcdWMxMWNcdWM3NTggXHViMmE1XHViODI1XHVjNzQ0IDBcdWJkODBcdWQxMzAgMTAwXHVhYzAwXHVjOWMwXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWMyMThcdWNlNThcdWQ2NTQgXHVkNTg4XHViMmU0LiAwXHVjNzQwIFx1YWRmOCBcdWMxMjBcdWMyMThcdWFjMDAgXHVhZGY4IFx1ZDNlY1x1YzljMFx1YzE1OFx1YzVkMCBcdWM4MDFcdWQ1NjlcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0XHViNTRjLCBcdWJhYThcdWI0ZTAgXHVjMTIwXHVjMjE4XHVjNzU4IFx1ZDNlY1x1YzljMFx1YzE1OFx1Yzc0NCBcdWM4MTVcdWQ1NzRcdWM5YzBcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViYWE4XHViNGUwIFx1ZDNlY1x1YzljMFx1YzE1OFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjMTIwXHVjMjE4XHVhYzAwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWMxMjBcdWMyMThcdWIyOTQgXHViMmE1XHViODI1XHVjZTU4XHVhYzAwIDBcdWM3NzggXHVkM2VjXHVjOWMwXHVjMTU4XHVjNWQwIFx1YmMzMFx1Y2U1OFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCAxMVx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBpXHViYzg4IFx1YzkwNFx1Yzc0MCAwXHVhY2ZjIDEwMFx1YzBhY1x1Yzc3NFx1Yzc1OCAxMVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggczxzdWI+aWo8XC9zdWI+XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIHM8c3ViPmlqPFwvc3ViPlx1YjI5NCBpXHViYzg4XHVjMTIwXHVjMjE4XHVhYzAwIGpcdWJjODggXHVkM2VjXHVjOWMwXHVjMTU4XHVjNWQwXHVjMTFjIFx1YjZmOCBcdWI1NGNcdWM3NTggXHViMmE1XHViODI1XHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMTIwXHVjMjE4XHVjNWQwXHVhYzhjIFx1YzgwMVx1ZDU2OVx1ZDU1YyBcdWQzZWNcdWM5YzBcdWMxNThcdWM3NTggXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCA1XHVhYzFjXHVjNzc0XHViMmU0LiAoXHViMmE1XHViODI1XHVjZTU4XHVhYzAwIDBcdWJjZjRcdWIyZTQgXHVkMDZjXHViMmU0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYWE4XHViNGUwIFx1ZDNlY1x1YzljMFx1YzE1OFx1Yzc1OCBcdWMxMjBcdWMyMThcdWI5N2MgXHVjYzQ0XHVjNmUwXHVjNzQ0IFx1YjU0YywgXHViMmE1XHViODI1XHVjZTU4XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgMVx1YWMxY1x1Yzc1OCBcdWM2MmNcdWJjMTRcdWI5NzggXHViNzdjXHVjNzc4XHVjNWM1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5ODAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMaW5ldXAiLCJkZXNjcmlwdGlvbiI6IjxwPk9uIEp1bmUgMTN0aCB0ZWFtIEdlcm1hbnkgaGFzIGl0cyBmaXJzdCBtYXRjaCBpbiB0aGUgRklGQSB3b3JsZCBjdXAgYWdhaW5zdCB0ZWFtIEF1c3RyYWxpYS4gQXMgdGhlIGNvYWNoIG9mIHRlYW0gR2VybWFueSwgaXQgaXMgeW91ciBkdXR5IHRvIHNlbGVjdCB0aGUgbGluZXVwIGZvciB0aGUgZ2FtZS4gR2l2ZW4gdGhpcyBpcyB5b3VyIGZpcnN0IGdhbWUgaW4gdGhlIGN1cCwgbmF0dXJhbGx5IHlvdSB3YW50IHRvIG1ha2UgYSBnb29kIGltcHJlc3Npb24uIFRoZXJlZm9yZSB5b3UmIzM5O2QgbGlrZSB0byBwbGF5IHdpdGggdGhlIHN0cm9uZ2VzdCBsaW5ldXAgcG9zc2libGUuPGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC80NDIucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjIyNnB4OyB3aWR0aDoxNzBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSBhbHJlYWR5IGRlY2lkZWQgb24gdGhlIHRhY3RpY2FsIGZvcm1hdGlvbiB5b3Ugd2lzaCB0byB1c2UsIHNvIG5vdyB5b3UgbmVlZCB0byBzZWxlY3QgdGhlIHBsYXllcnMgd2hvIHNob3VsZCBmaWxsIGVhY2ggb2YgdGhlIDExIHBvc2l0aW9ucyBpbiB0aGUgdGVhbS4gWW91ciBhc3Npc3RhbnQgaGFzIHNlbGVjdGVkIHRoZSAxMSBzdHJvbmdlc3QgcGxheWVycyBmcm9tIHlvdXIgc3F1YWQsIGJ1dCB0aGlzIHN0aWxsIGxlYXZlcyB0aGUgcXVlc3Rpb24gd2hlcmUgdG8gcHV0IHdoaWNoIHBsYXllci48XC9wPlxyXG5cclxuPHA+TW9zdCBwbGF5ZXJzIGhhdmUgYSBmYXZvdXJlZCBwb3NpdGlvbiBvbiB0aGUgZmllbGQgd2hlcmUgdGhleSBhcmUgc3Ryb25nZXN0LCBidXQgc29tZSBwbGF5ZXJzIGFyZSBwcm8gY2llbnQgaW4gZGlmZmVyZW50IHBvc2l0aW9ucy4gWW91ciBhc3Npc3RhbnQgaGFzIHJhdGVkIHRoZSBwbGF5aW5nIHN0cmVuZ3RoIG9mIGVhY2ggb2YgeW91ciAxMSBwbGF5ZXJzIGluIGVhY2ggb2YgdGhlIDExIGF2YWlsYWJsZSBwb3NpdGlvbnMgaW4geW91ciBmb3JtYXRpb24sIHdoZXJlIGEgc2NvcmUgb2YgMTAwIG1lYW5zIHRoYXQgdGhpcyBpcyBhbiBpZGVhbCBwb3NpdGlvbiBmb3IgdGhlIHBsYXllciBhbmQgYSBzY29yZSBvZiAwIG1lYW5zIHRoYXQgdGhlIHBsYXllciBpcyBub3Qgc3VpdGFibGUgZm9yIHRoYXQgcG9zaXRpb24gYXQgYWxsLiBGaW5kIHRoZSBsaW5ldXAgd2hpY2ggbWF4aW1pc2VzIHRoZSBzdW0gb2YgdGhlIHBsYXlpbmcgc3RyZW5ndGhzIG9mIHlvdXIgcGxheWVycyBmb3IgdGhlIHBvc2l0aW9ucyB5b3UgYXNzaWduZWQgdGhlbS4gQWxsIHBvc2l0aW9ucyBtdXN0IGJlIG9jY3VwaWVkLCBob3dldmVyLCBkbyBub3QgcHV0IHBsYXllcnMgaW4gcG9zaXRpb25zIHRoZXkgYXJlIG5vdCBwcm9maWNpZW50IHdpdGggKGkuZS4gaGF2ZSBhIHNjb3JlIG9mIDApLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gVGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBDIG9mIHRlc3QgY2FzZXMuIEZvciBlYWNoIGNhc2UgeW91IGFyZSBnaXZlbiAxMSBsaW5lcywgb25lIGZvciBlYWNoIHBsYXllciwgd2hlcmUgdGhlIGktdGggbGluZSBjb250YWlucyAxMSBpbnRlZ2VyIG51bWJlcnMgczxzdWI+aWo8XC9zdWI+IGJldHdlZW4gMCBhbmQgMTAwLiBzPHN1Yj5pajxcL3N1Yj4gZGVzY3JpYmVzIHRoZSBpLXRoIHBsYXllciYjMzk7cyBzdHJlbmd0aCBvbiB0aGUgai10aCBwb3NpdGlvbi4gTm8gcGxheWVyIHdpbGwgYmUgcHJvZmljaWVudCBpbiBtb3JlIHRoYW4gdmUgZGkgZXJlbnQgcG9zaXRpb25zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgdGhlIG1heGltdW0gb2YgdGhlIHN1bSBvZiBwbGF5ZXIgc3RyZW5ndGhzIG92ZXIgYWxsIHBvc3NpYmxlIGxpbmV1cHMuIEVhY2ggdGVzdCBjYXNlIHJlc3VsdCBzaG91bGQgZ28gb24gYSBzZXBhcmF0ZSBsaW5lLiBUaGVyZSB3aWxsIGFsd2F5cyBiZSBhdCBsZWFzdCBvbmUgdmFsaWQgbGluZXVwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==