往届 ACM 队训练题 (参考)

1008. 游戏

单点时限: 2.0 sec

内存限制: 256 MB

太阳 GG 在玩一个游戏,给一张 $n \times m$ 的地图,$n$ 行 $m$ 列,有 $k$ 个小强在这个地图中,对于每行有 $n$ 把枪,选择这把枪,可以将这列的小强都 kill 掉,对于 $m$ 列也同样,对于每把枪,有个损失值,现在要求太阳 GG kill 掉地图中所有的小强,且使得所选的枪的损失值的乘积最小。

输入格式

多 case。输入 $n,m,k$ ($1 \le n \le 100, 1 \le m \le 100, 1 \le k \le 2000$)

接下来一行有 $n$ 个数,代表选择每行枪的损失值 ( $> 1.0$ )

再接下来一行有 $m$ 个数,代表选择每列枪的损失值 ( $> 1.0$ )

接下来 $k$ 行,每行 2 个数,代表小强的坐标

输出格式

输出 kill 小所有小强选择枪的损失值的乘积 (4 位有效数字), 并且使得这个乘积最小

样例

Input
4 4 5
1.2 4.2 6.0 7.6
2.2 3.7 6.1 2.1
3 3
1 4
1 4
1 4
2 1
Output
15.8400
不限期开放

题目列表