Multi-Element Binary Search Tree

A multi-element binary search tree differs from an ordinary binary search tree in that each node may hold several elements. The core binary-search-tree condition still holds in a generalized form: for any node, every element in that node's left subtree must be smaller, and every element in its right subtree larger, than every element the node itself contains.

Therefore an element can be looked up in a multi-element binary search tree in exactly the same way as in an ordinary one. At each node we decide whether the sought element must be in this node, or whether to descend into the left or the right subtree. Counting each such decision as one operation, the number of operations needed to reach the node that holds a given element equals exactly the number of levels from the root down to that node (the root is at level $1$).

Because of how node memory is managed, the maximum number of elements a single node may hold differs from level to level. With the root at level $1$, the maximum number of elements $m_i$ in a node at level $i$ is defined, for given integers $M$, $K$, and $D_j$, by

$m_i = \begin{cases} M & (i = 1) \\ \max\bigl(1,\ m_{i-1} - D_{((i-2) \bmod K) + 1}\bigr) & (i > 1) \end{cases}$

That is, the value $D_j$ subtracted when descending one level cycles as $D_1$ at level $2$, $D_2$ at level $3$, $\ldots$, $D_K$ at level $K+1$, then $D_1$ again at level $K+2$, and so on. For example, if $M = 4$, $K = 2$, $D_1 = 1$, $D_2 = 2$, then the root may hold at most $m_1 = M = 4$ elements, each of its direct children at most $m_2 = m_1 - D_1 = 4 - 1 = 3$, each of their children $m_3 = m_2 - D_2 = 3 - 2 = 1$, and every deeper node at most $m_i = 1$ element.

Moreover, different elements are searched for with different probabilities, so a balanced tree does not necessarily minimize the average lookup time. For instance, if the smallest element is searched for far more often than any other, it is advantageous to place it at the root, in which case the entire left subtree stays empty.

For the given set of elements and their search probabilities, find the minimum average number of operations per lookup over all optimally shaped multi-element binary search trees.

The first line contains three integers $N$, $M$, and $K$, where $N$ is the number of elements ($1 \le N \le 100$), $1 \le M \le N$, and $1 \le K \le N$. Each of the next $K$ lines contains one integer: the value on line $j+1$ is $D_j$ ($0 \le D_j \le M$). The last line contains $N$ real numbers $P_i$ ($0 \le P_i \le 1$ and $\sum_{i=1}^{N} P_i = 1$), the search probability of each element. The probabilities are listed in order of element value (the first probability belongs to the smallest element). The actual element values do not matter for the solution; you may assume they are all distinct.

Print, on a single line, the minimum average number of operations per lookup in an optimally shaped tree, rounded to exactly $7$ digits after the decimal point.

The optimal tree shape for the second test case is shown below.