Bear and Shop Trip

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Bear Limak is an assistant in the kitchen. While he doesn't really know how to cook, he can run very fast and thus Chef often sends him to buy new ingredients from shops.
Chef needs K different ingredients, numbered 1 through K.
The kitchen is located at the point (0, 0). There are N shops. The ith shop is located at the point (X_{i}, Y_{i}) and its inventory is described by the string s_{i} of length K. The ith character of s_{i} is '1' if the ith ingredient is available in this shop, and '0' otherwise.
All N+1 points are distinct (the kitchen and the N shops).
Limak must start from the kitchen, visit some shops and buy all necessary ingredients (each of K ingredients should be available in at least one visited shop), and go back to the kitchen. What is the minimum total distance Limak will cover? Print 1 if it's impossible to get all the ingredients.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two integers N and K denoting the number of shops and the number of ingredients.
The ith of the next N lines contains two integers x_{i} and y_{i} denoting coordinates of the ith shop. No two shops are at the same point, and no shop is at the point (0, 0).
The ith of the next N lines contains a string s_{i} of length K, consisting of characters '1' and '0'. The jth character is '1' if and only if the jth ingredient is available in this shop.
Output
For each test case, output a single line containing the answer: a number 1 if Limak can't get all K ingredients, or one real value otherwise — the minimum total distance. The relative or absolute error shouldn't exceed 10^{6}.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 36
 1 ≤ K ≤ 12
 1000 ≤ x_{i}, y_{i} ≤ 1000
Example
Input: 5 3 6 100 100 50 100 0 100 111110 110011 001111 3 6 100 100 50 100 0 100 111110 110011 111111 3 6 100 100 50 100 0 210 111110 110011 111111 3 6 100 100 50 100 0 210 111010 110011 111011 10 10 763 77 512 859 494 362 986 885 866 890 128 553 879 981 449 310 406 10 955 475 0000001000 1000000000 0000000100 0001000000 0000100000 0010000000 0000010000 0000000001 0100000000 0000000010 Output: 403.2247551123 200.0000000000 403.2247551123 1 6652.7837723893
Explanation
Test case 1. There are 3 shops, located at points (100, 100), (50, 100) and (0, 100). The first shop is described by a string "111110", which means that ingredients 1 through 5 are available in this shop, but ingredient 6 isn't. The other two shops are described by strings "110011" and "001111" respectively. Any two shops are enough to get all 6 ingredients (because, for every two shops it's true that each of 6 ingredients is available in at least one of those two shops).
To minimize the total distance, Limak should visit the first and the second shop (in any order). For example, his journey can look as follows:
 Go from the starting point (0, 0) to the first shop (100, 100). The distance is sqrt(100^{2} + 100^{2}) = 141.4213562373095.
 Go from (100, 100) to (50, 100). The distance is 150.
 Go from (50, 100) back to the kitchen at (0, 0). The distance is sqrt(50^{2} + 100^{2}) = 111.80339887498948
The total distance is 141.4213562373095 + 150 + 111.80339887498948 = 403.224755112299.
Test case 2. This time the third shop has all the ingredients. It's optimal to visit only this shop and go back to the kitchen.
Test case 4. Limak can't get all ingredients, even if he visits all the shops. The answer is 1.
Author:  errichto 
Tester:  mnbvmar 
Editorial  https://discuss.codechef.com/problems/SHOPTRIP 
Tags  cook81, dp+bitmask, easy, errichto 
Date Added:  20042017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 