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

문제

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 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+XHJcblx0XHVjNzc0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWQzZWNcdWM5YzBcdWMxNThcdWM3NDQgXHVjODE1XHVkNTc0XHVjOWMwXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmFhOFx1YjRlMCBcdWQzZWNcdWM5YzBcdWMxNThcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzEyMFx1YzIxOFx1YWMwMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWFjMDEgXHVjMTIwXHVjMjE4XHViMjk0IFx1YjJhNVx1YjgyNVx1Y2U1OFx1YWMwMCAwXHVjNzc4IFx1ZDNlY1x1YzljMFx1YzE1OFx1YzVkMCBcdWJjMzBcdWNlNThcdWI0MjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMTFcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgaVx1YmM4OCBcdWM5MDRcdWM3NDAgMFx1YWNmYyAxMDBcdWMwYWNcdWM3NzRcdWM3NTggMTFcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHM8c3ViPmlqPFwvc3ViPlx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBzPHN1Yj5pajxcL3N1Yj5cdWIyOTQgaVx1YmM4OFx1YzEyMFx1YzIxOFx1YWMwMCBqXHViYzg4IFx1ZDNlY1x1YzljMFx1YzE1OFx1YzVkMFx1YzExYyBcdWI2ZjggXHViNTRjXHVjNzU4IFx1YjJhNVx1YjgyNVx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzEyMFx1YzIxOFx1YzVkMFx1YWM4YyBcdWM4MDFcdWQ1NjlcdWQ1NWMgXHVkM2VjXHVjOWMwXHVjMTU4XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgNVx1YWMxY1x1Yzc3NFx1YjJlNC4gKFx1YjJhNVx1YjgyNVx1Y2U1OFx1YWMwMCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YmFhOFx1YjRlMCBcdWQzZWNcdWM5YzBcdWMxNThcdWM3NTggXHVjMTIwXHVjMjE4XHViOTdjIFx1Y2M0NFx1YzZlMFx1Yzc0NCBcdWI1NGMsIFx1YjJhNVx1YjgyNVx1Y2U1OFx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIDFcdWFjMWNcdWM3NTggXHVjNjJjXHViYzE0XHViOTc4IFx1Yjc3Y1x1Yzc3OFx1YzVjNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTgwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGluZXVwIiwiZGVzY3JpcHRpb24iOiI8cD5PbiBKdW5lIDEzdGggdGVhbSBHZXJtYW55IGhhcyBpdHMgZmlyc3QgbWF0Y2ggaW4gdGhlIEZJRkEgd29ybGQgY3VwIGFnYWluc3QgdGVhbSBBdXN0cmFsaWEuIEFzIHRoZSBjb2FjaCBvZiB0ZWFtIEdlcm1hbnksIGl0IGlzIHlvdXIgZHV0eSB0byBzZWxlY3QgdGhlIGxpbmV1cCBmb3IgdGhlIGdhbWUuIEdpdmVuIHRoaXMgaXMgeW91ciBmaXJzdCBnYW1lIGluIHRoZSBjdXAsIG5hdHVyYWxseSB5b3Ugd2FudCB0byBtYWtlIGEgZ29vZCBpbXByZXNzaW9uLiBUaGVyZWZvcmUgeW91JiMzOTtkIGxpa2UgdG8gcGxheSB3aXRoIHRoZSBzdHJvbmdlc3QgbGluZXVwIHBvc3NpYmxlLjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvNDQyLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMjZweDsgd2lkdGg6MTcwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgYWxyZWFkeSBkZWNpZGVkIG9uIHRoZSB0YWN0aWNhbCBmb3JtYXRpb24geW91IHdpc2ggdG8gdXNlLCBzbyBub3cgeW91IG5lZWQgdG8gc2VsZWN0IHRoZSBwbGF5ZXJzIHdobyBzaG91bGQgZmlsbCBlYWNoIG9mIHRoZSAxMSBwb3NpdGlvbnMgaW4gdGhlIHRlYW0uIFlvdXIgYXNzaXN0YW50IGhhcyBzZWxlY3RlZCB0aGUgMTEgc3Ryb25nZXN0IHBsYXllcnMgZnJvbSB5b3VyIHNxdWFkLCBidXQgdGhpcyBzdGlsbCBsZWF2ZXMgdGhlIHF1ZXN0aW9uIHdoZXJlIHRvIHB1dCB3aGljaCBwbGF5ZXIuPFwvcD5cclxuXHJcbjxwPk1vc3QgcGxheWVycyBoYXZlIGEgZmF2b3VyZWQgcG9zaXRpb24gb24gdGhlIGZpZWxkIHdoZXJlIHRoZXkgYXJlIHN0cm9uZ2VzdCwgYnV0IHNvbWUgcGxheWVycyBhcmUgcHJvIGNpZW50IGluIGRpZmZlcmVudCBwb3NpdGlvbnMuIFlvdXIgYXNzaXN0YW50IGhhcyByYXRlZCB0aGUgcGxheWluZyBzdHJlbmd0aCBvZiBlYWNoIG9mIHlvdXIgMTEgcGxheWVycyBpbiBlYWNoIG9mIHRoZSAxMSBhdmFpbGFibGUgcG9zaXRpb25zIGluIHlvdXIgZm9ybWF0aW9uLCB3aGVyZSBhIHNjb3JlIG9mIDEwMCBtZWFucyB0aGF0IHRoaXMgaXMgYW4gaWRlYWwgcG9zaXRpb24gZm9yIHRoZSBwbGF5ZXIgYW5kIGEgc2NvcmUgb2YgMCBtZWFucyB0aGF0IHRoZSBwbGF5ZXIgaXMgbm90IHN1aXRhYmxlIGZvciB0aGF0IHBvc2l0aW9uIGF0IGFsbC4gRmluZCB0aGUgbGluZXVwIHdoaWNoIG1heGltaXNlcyB0aGUgc3VtIG9mIHRoZSBwbGF5aW5nIHN0cmVuZ3RocyBvZiB5b3VyIHBsYXllcnMgZm9yIHRoZSBwb3NpdGlvbnMgeW91IGFzc2lnbmVkIHRoZW0uIEFsbCBwb3NpdGlvbnMgbXVzdCBiZSBvY2N1cGllZCwgaG93ZXZlciwgZG8gbm90IHB1dCBwbGF5ZXJzIGluIHBvc2l0aW9ucyB0aGV5IGFyZSBub3QgcHJvZmljaWVudCB3aXRoIChpLmUuIGhhdmUgYSBzY29yZSBvZiAwKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIFRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBudW1iZXIgQyBvZiB0ZXN0IGNhc2VzLiBGb3IgZWFjaCBjYXNlIHlvdSBhcmUgZ2l2ZW4gMTEgbGluZXMsIG9uZSBmb3IgZWFjaCBwbGF5ZXIsIHdoZXJlIHRoZSBpLXRoIGxpbmUgY29udGFpbnMgMTEgaW50ZWdlciBudW1iZXJzIHM8c3ViPmlqPFwvc3ViPiBiZXR3ZWVuIDAgYW5kIDEwMC4gczxzdWI+aWo8XC9zdWI+IGRlc2NyaWJlcyB0aGUgaS10aCBwbGF5ZXImIzM5O3Mgc3RyZW5ndGggb24gdGhlIGotdGggcG9zaXRpb24uIE5vIHBsYXllciB3aWxsIGJlIHByb2ZpY2llbnQgaW4gbW9yZSB0aGFuIHZlIGRpIGVyZW50IHBvc2l0aW9ucy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IHRoZSBtYXhpbXVtIG9mIHRoZSBzdW0gb2YgcGxheWVyIHN0cmVuZ3RocyBvdmVyIGFsbCBwb3NzaWJsZSBsaW5ldXBzLiBFYWNoIHRlc3QgY2FzZSByZXN1bHQgc2hvdWxkIGdvIG9uIGEgc2VwYXJhdGUgbGluZS4gVGhlcmUgd2lsbCBhbHdheXMgYmUgYXQgbGVhc3Qgb25lIHZhbGlkIGxpbmV1cC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=