In a card game consisting of r rounds, you have n cards. Each card has a score ai, and the probability of successfully using card i is pi. In each round:
- Start from the first card (1,2,...,n).
- If the card is already used, move to the next card.
- If the card is unused:
- With probability pi, the card is successfully used, and the round ends.
- With probability 1−pi, the card fails to be used, so move to the next card.
- If all cards are exhausted without success, proceed to the next round.
You are tasked to calculate the expected value of the total score obtained after r rounds.
### Input
- The first line contains an integer T, the number of test cases.
- For the next T datasets:
- The first line contains two integers n,r.
- The next n lines each contain two numbers pi,ai.
### Output
- Print a floating-point number representing the expected total score, rounded to at least 6 decimal places.
### Constraints
- 1≤T≤500.
- 1≤n≤222.
- 1≤r≤133.
- 0<pi<1.
- 1≤ai≤1000.
### Sample Test
Input:
1320.400020.300030.80001
Output
3.0814240000
