#P1461C. Random Events
Random Events
No submission language available for this problem.
Description
Ron is a happy owner of a permutation of length .
A permutation of length is an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, but is not a permutation ( appears twice in the array) and is also not a permutation ( but there is in the array).

Ron's permutation is subjected to experiments of the following type: (, ). This means that elements in range (in other words, the prefix of length ) have to be sorted in ascending order with the probability of . All experiments are performed in the same order in which they are specified in the input data.
As an example, let's take a look at a permutation and an experiment (). After such an experiment with the probability of the permutation will assume the form and with a probability it will remain unchanged.
You have to determine the probability of the permutation becoming completely sorted in ascending order after experiments.
Each test contains one or more test cases. The first line contains the number of test cases ().
The first line of each test case contains two integers and — the length of the permutation and the number of experiments, respectively.
The second line of each test case contains integers — contents of the permutation.
The following lines of each test case each contain an integer and a real number — the length of the prefix and the probability of it being sorted. All probabilities are given with at most decimal places.
It is guaranteed that the sum of and the sum of does not exceed ().
For each test case, print a single number — the probability that after all experiments the permutation becomes sorted in ascending order. Your answer will be considered correct if its absolute or relative error does not exceed .
Formally, let your answer be , and the jury's answer be . Your answer is accepted if and only if .
Input
Each test contains one or more test cases. The first line contains the number of test cases ().
The first line of each test case contains two integers and — the length of the permutation and the number of experiments, respectively.
The second line of each test case contains integers — contents of the permutation.
The following lines of each test case each contain an integer and a real number — the length of the prefix and the probability of it being sorted. All probabilities are given with at most decimal places.
It is guaranteed that the sum of and the sum of does not exceed ().
Output
For each test case, print a single number — the probability that after all experiments the permutation becomes sorted in ascending order. Your answer will be considered correct if its absolute or relative error does not exceed .
Formally, let your answer be , and the jury's answer be . Your answer is accepted if and only if .
Samples
Note
Explanation of the first test case: It can be demonstrated that whether the final permutation is sorted or not depends solely on sorting being performed in the experiment.