Bill is a millionaire. But unfortunately he was trapped in a castle. There are only n passages to go out. For any passage i (1<=i<=n), Pi (0<=Pi<=1) denotes the probability that Bill will escape from this castle safely if he chose this passage. Qi (0<=Qi<=1-Pi) denotes the probability that there is a group of guards in this passage. And Bill should give them one million dollars and go back. Otherwise, he will be killed. The probability of this passage had a dead end is 1-Pi-Qi. In this case Bill has to go back. Whenever he came back, he can choose another passage.

We already know that Bill has M million dollars. Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.

We already know that Bill has M million dollars. Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.

The first line contains an integer T (T<=100) indicating the number of test cases.

The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).

Then n lines follows, each line contains two float number Pi and Qi.

The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).

Then n lines follows, each line contains two float number Pi and Qi.

提交代码