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.