Problem: flow2
Now that Christams is over, Christmas town has quiet down and life is peaceful again. Santa's group of elves has decided that they should celebrate yet another successful Christmas. To do so, they have decided to bake an extra large cake.
Baking a cake takes several phases and must be done sequentially. That is, phase 1 must be completed before phase 2 and so forth. The elves has decided to split the work amongst themselves by assigning an elf to each phase.
However, there are some problems. First, not all elves know how to do every phase. Second, each elf works in a different speed. All phases are equivalent in terms of the work required, so if an elf takes 5 minutes to finish phase 1, it'll also take 5 minutes to finish phase 2 (assuming the elf are able to do both phases). Finally, elves do get tired. So the more phases that are assigned to the same elf, the longer time it take for the elf to complete all the phases. In particular, if an elf is responsible for k phases and can complete a single phase (disregarding fatigue) in 5 minutes, then the total time it takes to complete all k phases is 5k2 minutes. In other word, if the elf is already responsible for k phases, assigning an additional phase to the elf will take an additional 5(2*k+1) minutes. The task given to you is to assign an elf to each phase to minimize the total amount of time to make the cake.
For example, suppose the cake takes 3 phases and you have two elves at your disposal. The first elf can finish a phase (disregarding fatigue) in 3 minutes and know how to do all the phases. The second elf can finish a phase (disregarding fatigue) in 10 minutes and only know how to do the last 2 phases. Then the minimal amount of time to make the cake is to assign phase 1 and 2 to the first elf, taking a total 22×3 = 12 minutes, and assign the last phase to the second elf, taking 10 minutes. The minimum amount of time it takes is then 22 minutes.
Input
The first line of the input will contain an integer, indicating the number of test cases that follow. For each of the test case, the first line will contain two integers m and n, the number of phases and elves respectively. Each of the next n lines will describe each of the elves. The first integer on each line indicate the number of minutes it takes for the elf to complete a single phase (disregarding fatigue). Next follows m integers, describing which phases the elf can complete. The ith integer is 1 if the elf can complete phase i and 0 otherwise.
Bounds
For each test case, 1 ≤ m ≤ 20 and 1 ≤ n ≤ 20. The maximum number of minutes it takes for an elf to complete a single phase (disregarding fatigue) is 5000000.
Output
For each test case, output a single integer on its own line, indicating the minimum amount of time it takes to complete the cake. Output -1 if the cake cannot be completed.
Sample Input
3 3 2 3 1 1 1 10 0 1 1 4 2 1 1 1 1 1 10 0 1 1 0 4 1 10 0 0 1 1
Sample Output
22 16 -1