5013：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.