LINEUP - Lineup

no tags 

On June 13th team Germany has its first match in the FIFA world cup against team Australia. As the coach of team Germany, it is your duty to select the lineup for the game. Given this is your first game in the cup, naturally you want to make a good impression. Therefore you'd like to play with the strongest lineup possible.

example image

 

You have already decided on the tactical formation you wish to use, so now you need to select the players who should fill each of the 11 positions in the team. Your assistant has selected the 11 strongest players from your squad, but this still leaves the question where to put which player.

Most players have a favoured position on the field where they are strongest, but some players are proficient in different positions. Your assistant has rated the playing strength of each of your 11 players in each of the 11 available positions in your formation, where a score of 100 means that this is an ideal position for the player and a score of 0 means that the player is not suitable for that position at all. Find the lineup which maximises the sum of the playing strengths of your players for the positions you assigned them. All positions must be occupied, however, do not put players in positions they are not proficient with (i.e.\ have a score of 0).

Input

The input consists of several test cases. The first line of input contains the number C of test cases. For each case you are given 11 lines, one for each player, where the i-th line contains 11 integer numbers sij between 0 and 100. sij describes the i-th player's strength on the j-th position. No player will be proficient in more than five different positions.

Output

For each test case output the maximum of the sum of player strengths over all possible lineups. Each test case result should go on a separate line. There will always be at least one valid lineup.

Example

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

Output:
970

hide comments
horro: 2020-06-19 15:24:09

DP+bitmask in 0.00s: consider negative cases+all players must be chosen their position

nadstratosfer: 2020-02-23 14:27:45

There are no negative values in input and like the statement says, there is always a valid lineup. My pitfall was initializing the temporary result too high however, so even though my program wouldn't produce a result from incomplete squad, it did memoize a positive value and prevent a correct setup from being found. What a headache.

Last edit: 2020-02-23 14:30:15
codercodecoder: 2020-02-22 17:59:13

I am new to dp as well competitive programming.Could any one tell how to approach the solution

scolar_fuad: 2020-01-06 16:03:23

one corner case many of you will miss is that even some permuation will not produce line of 11 but give maximum result

kesucool: 2017-01-28 21:02:04

good problem ...take care do not put players in the position they are not proficient with ;)

devbishnoi: 2016-11-20 09:00:17

be careful with negative strengths , It may be possible that total strength will be less than zero .

Last edit: 2016-11-20 09:00:46
coder_shishir: 2016-01-14 11:20:06

AC after too much struggle......0.01s....consider -ve values..

Last edit: 2016-01-14 11:20:27
Crazy Monk : 2015-08-13 20:21:43

2 WA's .. Didn't consider neg. values. Why were there negative values anyway..

fresh: 2015-05-06 06:30:52

consider the negative values of sij -_-

Nikhil Khurana: 2015-03-28 15:24:19

AC in first go :D


Added by:Adrian Kuegel
Date:2010-06-21
Time limit:1.266s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:German Collegiate Programming Contest 2010 (Author: Holger Frydrych)