How to calculate the expected cost?

Question

I am not good at probability and I know it's not a coding problem directly. But I wish you would help me with this. While I was solving a computation problem I found this difficulty:

Problem definition:

The Little Elephant from the Zoo of Lviv is going to the Birthday Party of the Big Hippo tomorrow. Now he wants to prepare a gift for the Big Hippo. He has N balloons, numbered from 1 to N. The i-th balloon has the color Ci and it costs Pi dollars. The gift for the Big Hippo will be any subset (chosen randomly, possibly empty) of the balloons such that the number of different colors in that subset is at least M. Help Little Elephant to find the expected cost of the gift.

Input

The first line of the input contains a single integer T - the number of test cases. T test cases follow. The first line of each test case contains a pair of integers N and M. The next N lines contain N pairs of integers Ci and Pi, one pair per line.

Output

In T lines print T real numbers - the answers for the corresponding test cases. Your answer will considered correct if it has at most 10^-6 absolute or relative error.

Example

Input:

2

2 2

1 4

2 7

2 1

1 4

2 7

Output:

11.000000000

7.333333333

So, Here I don't understand why the expected cost of the gift for the second case is 7.333333333, because the expected cost equals Summation[xP(x)] and according to this formula it should be 33/2?

Yes, it is a codechef question. But, I am not asking for the solution or the algorithm( because if I take the algo from other than it would not increase my coding potentiality). I just don't understand their example. And hence, I am not being able to start thinking about the algo.

Please help. Thanks in advance!

Answer 1

There are three possible choices, 1, 2, 1+2, with costs 4, 7 and 11. Each is equally likely, so the expected cost is (4 + 7 + 11) / 3 = 22 / 3 = 7.33333.