선발 명단

시간 제한1초메모리 제한128 MB

요약
11명의 선수를 11개 포지션에 배정해 능력치 합을 최대로 만든다. 능력치가 0인 자리는 쓸 수 없고, 각 선수가 적합한 포지션은 5개 이하다.
난이도

보통10점 중 6점

유형
백트래킹, 완전 탐색, 구현, 재귀
정답자
아직 제출이 없습니다

문제

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

결승에 나설 선발 선수 11명은 이미 골랐지만, 어느 선수를 어느 포지션에 세울지는 아직 정하지 못했다.

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

11개의 포지션에 모두 선수를 한 명씩 배치하되, 어떤 선수도 능력치가 00인 포지션에는 세울 수 없다. 이때 배치된 선수들의 능력치 합이 최대가 되도록 하는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 CC가 주어진다. 각 케이스는 11줄로 이루어지며, ii번째 줄에는 00 이상 100100 이하의 정수 11개 sijs_{ij}가 주어진다. sijs_{ij}는 ii번 선수가 jj번 포지션에서 뛸 때의 능력치이다. 모든 선수에 대해, 능력치가 00보다 큰 포지션(즉 적합한 포지션)의 수는 최대 5개이다.

출력

각 테스트 케이스마다, 11개의 포지션을 모두 채웠을 때 얻을 수 있는 능력치 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 올바른 라인업을 하나 이상 만들 수 있다.

예제1

  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
    예상 출력
    970