Problem Description
There are m visitors coming to visit country A, and they plan to visit all n cities in the country one after another. The cities are numbered from 1 to n by the order they are visited. The visitors start their tour at city 1. Each day, for each visitor i, he has pi probability to go to next city(which means city number increases by 1), and 1 - pi probability to fall in love with current city and stay there till the end of tour. If a visitor reach city n, he will not move any more.
When visitor i reach city j, he get Hij units of happiness.For j > 1, suppose city j is visited by cj(cj>0) visitors and city j - 1 is visited by cj - 1(cj - 1 > 0) visitors, then each of cj city j's visitors will get extra units of happiness.
Let htot denote the total happiness of all visitors at the end of tour. Now you need to calculate the expectation of htot.
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains two integers m and n (1 ≤ m ≤ 16,1 ≤ n ≤ 16) , indicating the number of visitors and the number of cities respectively.
The second line contains m real numbers pi(0 ≤ pi ≤ 1)—the probability for the ith visitor to move to next city each day. The probabilities are given with at most 6 digits after decimal point.
Then there are m lines follow, each line contains n integers. The j-th integer of ith line denotes hij (1 ≤ hij ≤ 100).
Output
For each test case, print a single real number in a line, represents the expectation of htot. The answer will be considered valid if it differs from the correct one by at most 10-5.
Sample Input
3 1
0.1 0.2 0.3
10
20
30
3 3
0.5 0.5 0.5
1 1 1
1 1 1
1 1 1
4 4
0.1 0.4 0.2 0.3
7 2 18 10
2 6 9 5
4 4 19 17
7 3 13 17
Sample Output
60.0000000
6.84375000
34.230645587
