题目描述

$\text{Mr. Potato}$ 开了两家新店卖土豆。他买了 $N$ 袋土豆，其中第 $i$ 袋价值为 $c_i$，袋里有 $a_i$ 个土豆。他打算把这 $N$ 袋土豆整袋整袋地分在两个店里。

在每家店中，土豆的平均价格等于这家店里所有袋的土豆的总价比上土豆的个数。（注意是个数而不是袋数！）

设 $P_1$ 为第一家店的土豆平均价格，$P_2$ 为第二家店的土豆平均价格。$\text{Mr. Potato}$ 希望在至少有一家店里土豆袋数正好等于 $L$ 袋的情况下，最小化 $P_1\times P_2$ 的值。

输入格式

第一行包含两个整数 $N$ 和 $L$。

第二行包含 $N$ 个整数 $a_i$。

第三行包含 $N$ 个整数 $c_i$。

输出格式

第一行输出一个浮点数，为 $P_1\times P_2$ 的最小值，保留到小数点后三位。

3 1
3 2 1
1 2 3

0.556

3 2
2 2 2
3 3 3

2.250

提示

【数据范围】

对于 $30\%$ 的数据，$2\le N\le 20$。

对于 $100\%$ 的数据，$2\le N\le 100$，$1\le L< N$，$1\le a_i\le 100$，$1\le c_i\le 10^6$，$\sum\limits_{i=1}^{N} a_i\le 500$。

【题目来源】

题目译自 COCI 2015-2016 CONTEST #6 T5 KRUMPIRKO。

本题分值按 COCI 原题设置，满分 $140$。