You have a jug and mugs. The jug’s capacity is liters and the mug’s capacity is liters. Initially, the jug is filled with water.
You run a shop. When a customer asks for water, you have to follow these two steps sequentially:
You throw out all the mugs that have a capacity greater than the amount of water in the jug. If there are no mugs left, you close the shop. Otherwise, you go to step .
From the mugs you presently have, you choose a mug uniformly at random. After that, you fill the mug with liters of water from the jug and give it to the customer. So, the water in the jug reduces by liters. For some weird reason, the customers never give back the mugs to you. As a result, you become angry and throw out all the mugs that have the capacity liters.
What is the expected number of times you can serve the customers? Note that, the customers come to your shop until you close your shop.
Input starts with an integer , the number of test cases.
In each test case, the first line contains two space-separated integers and , the number of mugs, and the jug's capacity.
The next line contains space-separated integers. The integer denotes the capacity of the mug.
Scoring
Subtask 1 (35 Points):
Subtask 2 (65 Points):
The sum of over all test cases doesn’t exceed .
For each test case, in a line, print the expected number of times you can serve the customers. Your answer will be considered correct if the absolute or relative error doesn’t exceed .
Formally, let's assume that your answer is , and the answer of the jury is . Your answer will be considered correct if and only if .
Input | Output |
---|---|
2 3 10 10 3 6 2 5 5 5 | 1.333333 1.000000 |
Sample Case 1 Explanation:
There are only scenarios:
Scenario :
You give mug to the customer. Then you'll throw all other mugs as their capacity is less than mug .
Scenario :
You give mug to the customer. As there are no mugs that have a capacity less or equal to mug 's capacity, you won't throw out any. The jug has now liters of water.
When the customer asks for water, you'll throw out mug as its capacity is greater than the present amount of water in the jug. Then only mug is left and you will give it to this customer.
Scenario :
You give mug to the customer. As mug 's capacity is less than mug 's capacity, you'll throw out mug . The jug has now liters of water.
When the customer asks for water, you'll throw out mug as its capacity is greater than the present amount of water in the jug. As there are no mugs left, you'll close the shop and the customer won't be served.
So, the expected number of times you can serve the customers is =