City Tour

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 p_i probability to go to next city(which means city number increases by 1), and 1 - p_i 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 H_ij units of happiness.For j > 1, suppose city j is visited by c_j(c_j>0) visitors and city j - 1 is visited by c_{j - 1}(c_{j - 1} > 0) visitors, then each of c_j city j's visitors will get extra units of happiness.

Let h_tot denote the total happiness of all visitors at the end of tour. Now you need to calculate the expectation of h_tot.

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 p_i(0 ≤ p_i ≤ 1)—the probability for the i_th 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 h_ij (1 ≤ h_ij ≤ 100).

For each test case, print a single real number in a line, represents the expectation of h_tot. The answer will be considered valid if it differs from the correct one by at most 10^-5.

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

60.0000000
6.84375000
34.230645587

2014 ACM/ICPC Asia Regional Xi'an Online