Killing Gs

All submissions for this problem are available.
There are the big enemies for all chefs, that is, Gs (the plural form of G).
Chef Ciel find N Gs in her restaurant.
Ciel is very scared, and she is going to kill the Gs by using insecticides.
Here M insecticides are available,
and the price of the jth insecticide is C_{j}, and she can use the jth insecticide for all N Gs if she buys it.
Unfortunately Gs may have resistance to insecticides, so Gs may be still alive after using some insecticides.
But we know that if Ciel use the jth insecticide, the ith G will be dead with the probability P_{i,j}%, and these are statistically independent.
Chef Ciel would like to buy some insecticides, and then, Ciel may use the insecticides one by one.
Ciel hopes that the ith G will be dead with a probability at least 90%, for all i, after using all insecticides which she buys.
Your work is selecting a cheaper (cheapest is not necessary) set of distinct insecticides which she buys.
Don't forget that the set must kill the ith G with a probability at least 90% for all i.
Input
The first line contains an integer T, the number of test cases.
Then T test cases follow.
The first line for each test case has 2 integers N and M.
The next line has M integers C_{1}, C_{2}, ..., C_{M}.
Then next N lines have M integers P_{i,j}, that is the jth integer of the ith line.
Output
For each test case, you should print two lines.
The first line should have an integer K, the number of insecticides which Ciel buys.
The second line should have K integers, the numbers of insecticides which Ciel buys, in ascending order.
Constraints
T = 50 (except for Sample Input)
50 ≤ N ≤ 200 (except for Sample Input)
50 ≤ M ≤ 200 (except for Sample Input)
1 ≤ C_{j} ≤ 1000000 (10^{6})
0 ≤ P_{i,j} ≤ 90
The probability of killing the ith G is at least 90% for all i, if Ciel buys all insecticides.
Scoring
For each test case, the score is defined as (basic  your) / basic, where your is the cost of your set and basic is the cost of the set given by CKROACH_simplesolution.c.
If the score is negative, it is treated as 0.
Your objective is to maximize the total score.
Test Case Generation
There is only one input file for this problem. Each test case generated by the below method.
N, M and P_{i,j} are chosen uniformly at random such that they satisfy constraints.
After that, each P_{i,j} becomes 0 with the probability 0.75.
Then an integer x is chosen from the set {1, 2, 5, 10, 100} uniformly at random.
For each j (1 ≤ j ≤ M),
a real number y_{j} is chosen from [0, 1) uniformly at random,
and C_{j} is set at (x + y_{j}) * (P_{1,j} + P_{2,j} + ... + P_{N,j}) rounded to the nearest integer.
If C_{j} is less than 1, then C_{j} becomes 1.
If C_{j} is more than 1000000, then C_{j} becomes 1000000.
Finally, if the generated case does not satisfy the constraint "The probability of killing the ith G is at least 90% for all i, if Ciel buys all insecticides", this case is destroyed and do the above process once again.
A test case generator is available here.
Sample Input
2 2 3 100 100 190 90 0 90 0 90 90 1 5 10 20 40 60 85 10 20 40 60 85
Sample Output
1 3 2 3 5
Output details
In the first case, the third insecticide will kill the ith G with probability 90% for all i.
In the second case, after using the third and fifth insecticides,
G is still alive with the probability (1  40/100) * (1  85/100) = 0.6 * 0.15 = 0.09.
Therefore the set of the third and fifth insecticides will kill the G with the probability 91%.
The output for Sample Input of CKROACH_simplesolution.c is the following. (which is far from the optimal)
2 1 2 5 1 2 3 4 5
Author:  laycurse 
Tester:  subra 
Editorial  http://discuss.codechef.com/problems/CKROACH 
Tags  challenge, laycurse, may12 
Date Added:  21092011 
Time Limit:  4.75 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions