Minimizing Expected Escaping Sheep

Little Blue has m sheep standing in a row. The i-th sheep will run away with probability \(p_i\). To prevent this, Little Blue buys n enclosures. The i-th enclosure can cover a contiguous segment of at most \(l_i\) sheep, and any sheep inside an enclosure will not escape.

Note that not all enclosures need to be used, and they can be placed arbitrarily (i.e. not necessarily in the given order).

Little Blue wants to know: What is the minimum expected number of sheep that will run away if the enclosures are arranged optimally?

It is clear that if a sheep is not covered then its chance of escape counts, so the problem is equivalent to maximizing the total "protected probability" (i.e. sum of \(p_i\) of the sheep covered by enclosures) subject to the following constraint. If we choose a set of intervals (each corresponding to an enclosure) with lengths \(L_1, L_2, \dots, L_k\) then there must exist a reordering such that the \(j\)-th smallest interval length is at most \(b_j\), where \(b_1 \le b_2 \le \cdots \le b_n\) are the enclosures' capacities. An optimal strategy can be achieved by assigning enclosures in non-decreasing order of their capacities to intervals chosen in order along the line. In such a strategy, if we denote \(B\) as the sorted array of \(l_i\)'s then when using the j-th enclosure (for an interval covering animals in positions \(t+1 \ldots i\)), we require that \[ i - t \le B[j]. \]

Let \(S = \sum_{i=1}^m p_i\) be the total escape probability if no sheep is protected. If we can protect a total probability of \(P\) (by covering the corresponding sheep), then the answer is \(S-P\). Your task is to compute the minimum expected number of escaping sheep.

inputFormat

The input starts with a line containing two integers m and n (1 ≤ m, n ≤ 1000), the number of sheep and the number of enclosures respectively.

The second line contains m floating point numbers \(p_1, p_2, \dots, p_m\) (each between 0 and 1), where \(p_i\) is the probability that the i-th sheep runs away.

The third line contains n integers \(l_1, l_2, \dots, l_n\) (each at least 1), where \(l_i\) represents the maximum number of consecutive sheep that the i-th enclosure can cover.

outputFormat

Output a single floating point number: the minimum expected number of sheep that will run away if the enclosures are arranged optimally. The answer should be printed with at least 6 decimal places of precision.

sample

5 2
0.1 0.5 0.3 0.6 0.2
2 3

0.000000