E – Our Fair Contest!
In an ACM regional contest held
in Shiraz University, two problems A and B are given. The problems have positive
weights and the final score of a team is computed as the weighted sum of the
numbers of solved test-cases for the two problems. Only the best k teams will
advance to the world finals where the integer 1≤k≤n-1 is randomly
chosen from a uniform distribution by the ACM international headquarters and
announced only after the list of the team scores is submitted.
The weights of the problems
are not known to the participating teams prior to the end of the contest following
which the site manager will work out the weights so as to maximize the expected
number of qualifying teams from Shiraz University over the unknown value of k.
Given
the number of solved test-cases for each problem by each team, compute the
maximum possible value of the expected number of Shiraz University teams which
will compete in the final world competition.
Input
On the
first line of input is given an integer T of the number of test-cases. The
first line of each test-case contains two integers 1<n≤10,000, the
total number of teams, followed by m<20, the number of teams from Shiraz University.
For the next n lines, the ith line has the number of test-cases (not greater than 10,000)
solved by the ith team for problems A and B in the same order. The
first m lines are associated with the teams from Shiraz University.
Output
For
each test-case print on a new line the maximum possible value of the expected
number of teams from Shiraz University that will have berths in the world finals.
All values have to be printed in exactly 4 decimal places.
|
Sample
Input |
Sample
Output |
|||||||||||||||||||||||||||||||||||||||
|
|