Starting Lineup

Time limit1sMemory limit128 MB

Summary
Assign 11 players to 11 positions, each with ability 0 to 100, maximizing total ability while avoiding zero-ability slots; every player suits at most 5 positions.
Level

Medium6 of 10

Topics
Backtracking, Brute force, Implementation, Recursion
Solved
No attempts yet

Problem

Ahead of a Champions League final, Manchester United's celebrated manager Ferguson wants to use a 4-4-2 diamond formation.

The 11 starters for the final have already been chosen, but it is not yet decided which player goes to which position.

Assistant coach Mike Phelan rated each of the 11 players' ability in each position as an integer from 0 to 100. A 00 means the player is not suited to that position.

Assign exactly one player to each of the 11 positions so that every position is filled and no player is placed in a position where their ability is 00. Write a program that makes this assignment so that the total ability of the placed players is as large as possible.

Input

The input consists of several test cases. The first line contains the number of test cases CC. Each case consists of 11 lines; the ii-th line contains 11 integers sijs_{ij} between 00 and 100100, where sijs_{ij} is player ii's ability in position jj. For every player, the number of positions with ability greater than 00 (its suitable positions) is at most 5.

Output

For each test case, output on its own line the maximum total ability achievable when all 11 positions are filled. At least one valid lineup always exists.

Examples1

  1. Example 1

    Input
    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
    Expected output
    970