Little Elephant and Blocks

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Little Elephant from Zoo of Lviv has n (0based numeration) blocks consisted of 1x1x1 cubes in such way that the size of ith block is 1x1xA_{i}. Each of the blocks also has a color, which is a positive integer. The color of ith block is C_{i}. There will be no more than two blocks of the same color.
Little Elephant wants to stack the blocks in the stack. In order to do so, he choose some random permutation P of integers from 0 to n1, inclusive, and stacks all the blocks in order of P, i. e. at first he stacks P_{0}th block, then P_{1}th and so on.
After stacking Little Elephant has a sequence of size S consisted of cubes (0based numeration) in order from the stack, where S = A_{0} + A_{1} + ... + A_{n1}. Then he counts the number of such pairs of cubes with indices i and j that j  i = k and ith cube has same color as jth. Call this number as colorfulness of the corresponding permutation.
Help Little Elephant and for a given n, k and the description of blocks find the expected colorfulness, considering that permutation P is chosen randomly.
Input
First line of the input contains single integer T  the number of test cases. Then T test cases follow. First line of each test case contains pair of integers n and k. Next n lines of each test case contain pairs of integers A_{i} and C_{i}.
Output
In T lines print T numbers  the answers for the corresponding test cases. Your answer will considered correct if it has at most 10^{6} absolute or relative error.
Constraints
1 ≤ T ≤ 10
1 ≤ n ≤ 20
1 ≤ k ≤ 200
1 ≤ A_{i} ≤ 10
1 ≤ C_{i} ≤ n
There will be no three or more blocks of the same color in a single test case.
Example
Input: 1 7 5 3 1 2 2 2 1 4 3 1 2 1 3 4 4 Output: 0.9095238
Author:  witua 
Editorial  http://discuss.codechef.com/problems/LEBLOCKS 
Tags  combinatorics, dynamicprogramming, june14, medium, witua 
Date Added:  21032012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions