P84432

KRUMPIRKO

难度 6 级 动态规划入门 背包
讨论 统计 2通过 22提交 9.1%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

\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 的最小值,保留到小数点后三位。

样例

样例 1
输入
3 1
3 2 1
1 2 3
输出
0.556
样例 2
输入
3 2
2 2 2
3 3 3
输出
2.250

提示

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

来源

COCI 2015/2016

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交