8520: Task Computing

As it says, Time is Money, Efficiency is Life. A client has a computing task waiting for uploading to the cloud servers. However, due to the resource limits and many other tasks, a task usually cannot be worked on a single server but multiple servers, one after another. You, as an employee of a cloud server provider who specializes in task allocation, need to select several servers from a limited number of cloud servers to perform calculations. We know that even the same servers will perform differently in different environments.
There are $n$ cloud servers available in the vicinity of the client's region numbered from $1$ to $n$. The $i$-th cloud server has two parameters: wiw_iwi and pip_ipi, which indicate the computing power and transmission efficiency of that server, respectively. The supervisor requires that each task must be computed by exactly $m$ of these servers. The client's computational task is not parallelizable, so you must sequence the work of the $m$ servers to maximize the total computational efficiency. We define the total computational efficiency as follows:
i=1∑mwaij=0∏i−1paj

where a1,a2,…,ama_1,a_2,\ldots, a_ma1,a2,…,am (pairwise distinct, 1≤ai≤n1\le a_i \le n1≤ai≤n) are the servers you selected. For convenience, a0=0,p0=1a_0 = 0, p_0 = 1a0=0,p0=1.

The first line contains two integers $n,m$ (1≤n≤1051\le n\le 10^51≤n≤105, $1\le m\le \min (n,20)$), denoting the number of cloud servers and servers that you have to select.
The second line contains $n$ integers w1,w2,…,wnw_1,w_2,\ldots, w_nw1,w2,…,wn (1≤wi≤1091\le w_i \le 10^91≤wi≤109), denoting the servers' computing power.
The third line contains $n$ integers q1,q2,…,qnq_1,q_2,\ldots, q_nq1,q2,…,qn (8000≤qi≤120008000\le q_i \le 120008000≤qi≤12000), where pi=qi10000p_i = \frac{q_i}{10000}pi=qi/10000 denotes the $i$-th server's transmission efficiency.

Output a float number denoting the maximal total computational efficiency. Your answer is considered correct if the relative or absolute error between yours and the standard solution is not greater than 10−610^{-6}10−6.

5 2
1 2 3 4 5
12000 11000 10000 9000 8000

8.5000000000000000