Task Computing

题号：NC239611
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

See Problem N for PDF statements.

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: $w_i$ and $p_i$ , 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:

$\sum\limits_{i=1}^{m}w_{a_i}\prod\limits_{j=0}^{i-1}p_{a_j}$

where $a_1,a_2,\ldots, a_m$ (pairwise distinct, $1\le a_i \le n$ ) are the servers you selected. For convenience, $a_0 = 0, p_0 = 1$ .

输入描述:

The first line contains two integers  (, ), denoting the number of cloud servers and servers that you have to select.

The second line contains  integers  (), denoting the servers' computing power.

The third line contains  integers  (), where  denotes the -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 .

示例1

输入

复制

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

输出

复制

8.5000000000000000