Dining

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Sergey is visiting ChefTown  a town famous for its' restaurants with famous ChefLand's cuisine. Among the most recommended things to do in ChefTown is to taste ChefLand's all N national dishes. Sergey has decided to do it, but as the person who is fond of planning everything, he needs to plan his restaurants' visit's in advance.
He knows that he will stay in ChefTown for D days and each day he'll have a dinner in one of ChefTown's restaurants. It is always hard to say, whether a particular dish will appear in the restaurant on some particular day. But based on the internet reviews, he concluded that the probability that the ith dish will appear in the restaurant he's going to visit on the jth day is A_{i, j}.
On the other hand, everything is even more complicated. Sergey is a thin guy and thus unable to eat more than K dishes in a single day. That doesn't mean that he has to eat K dishes every day, but if he won't eat any dish at all during some day, he'll go to sleep hungry and displeased, so he wants to avoid such situations. Because of hard financial situation, he will have food only in restaurants and wants to taste all the dishes exactly once.
Now, in order to process all this information, Sergey asks you to help him. Please make a plan for him such that:
 In the plan, he will taste every dish exactly once.
 During any day, he will eat at least one dish, but no more than K dishes in total. Here we mean, that he will plan to eat no more than K dishes (and at least one dish), but note that he might fail in this because of unavailability of some dishes on a particular day.
 The total probability that all the dishes will be available on their planned days of eating is maximal.
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 single spaceseparated integers N, D and K denoting the number of dishes that Sergey wants to taste, the number of days he'll stay in ChefTown and the maximum number of dishes he can eat during a single day respectively.
The following N lines will contain D spaceseparated real numbers each, where the jth real number in the ith line denotes the probability that the dish numbered ith will be available in the restaurant that he will visit during the jth day.
Output
For each test case, output two lines.
 The first line should contain maximal possible probability of eating all the dishes. Your answer will be considered as correct if it has an absolute error less than 1e−6 (ie. 10^{6}).
 The second line should contain N spaceseparated integers, describing the plan. The ith integer should describe the 1indexed number of day, during which the ith dish will be eaten. If there are more than one such possible plans, you can print any one of them.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 50
 1 ≤ D, K ≤ N
 D*K ≥ N
 0.750 ≤ A_{i, j} ≤ 1.000
 The probabilities will be given with no more than 3 digits after the decimal point.
Example
Input: 1 3 3 1 1.0 1.0 0.8 0.8 1.0 1.0 0.8 0.8 0.8 Output: 0.8 1 2 3
Explanation
Example case 1.On the first day, Sergey will eat the first dish. On the second day, he'll eat the second dish. On the third day, he'll try eat the third dish that will appear with the probability of 0.8. The total probability of dishes being available on these days is 0.8. It is impossible to achieve the better result.
Author:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/DINING 
Tags  graphs, mincostflow, snck151a, xcwgf666 
Date Added:  13052015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
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. 