github.com/captn3m0/codechef.git

---
category_name: challenge
problem_code: CKROACH
problem_name: 'Killing Gs'
languages_supported:
    - C
    - CPP14
    - JAVA
    - PYTH
    - 'PYTH 3.5'
    - CS2
    - 'PAS fpc'
    - 'PAS gpc'
    - RUBY
    - PHP
    - GO
    - NODEJS
    - 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
max_timelimit: '4.75'
source_sizelimit: '50000'
problem_author: laycurse
problem_tester: subra
date_added: 21-09-2011
tags:
    - challenge
    - laycurse
    - may12
editorial_url: 'http://discuss.codechef.com/problems/CKROACH'
time:
    view_start_date: 1336722913
    submit_start_date: 1336722913
    visible_start_date: 1336728600
    end_date: 1735669800
    current: 1525454416
is_direct_submittable: false
layout: problem
---
All submissions for this problem are available.There are the big enemies for all chefs, that is, _G_s (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 **j**-th insecticide is **Cj**, and she can use the **j**-th 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 **j**-th insecticide, the **i**-th 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 **i**-th 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 **i**-th 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, ..., **CM**. Then next **N** lines have **M** integers **P****i**,**j**, that is the **j**-th integer of the **i**-th 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 ≤ **Cj** ≤ 1000000 (106)
0 ≤ **P****i**,**j** ≤ 90
The probability of killing the **i**-th 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](http://www.codechef.com/download/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 **Cj** is less than 1, then **Cj** becomes 1. If **Cj** is more than 1000000, then **Cj** becomes 1000000.

Finally, if the generated case does not satisfy the constraint "The probability of killing the **i**-th 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](http://www.codechef.com/download/CKROACH_generator.c).

### Sample Input

<pre>2
2 3
100 100 190
90 0 90
0 90 90
1 5
10 20 40 60 85
10 20 40 60 85
</pre>### Sample Output

<pre>1
3
2
3 5
</pre>### Output details

In the first case, the third insecticide will kill the **i**-th 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](http://www.codechef.com/download/CKROACH_simplesolution.c) is the following. (which is far from the optimal)

<pre>2
1 2
5
1 2 3 4 5
</pre>