题目描述

公元$2500$年，地球与火星爆发激烈战争。地球指挥官通过间谍获悉，火星人计划在某个主要武器工厂的$m \times n$网格空降场投放伞兵，每个伞兵的着陆坐标已知。由于伞兵战斗力极强且组织严密，即使仅存一名伞兵也能摧毁整个工厂。因此，地球防御部队必须在伞兵着陆后同时消灭所有伞兵。

防御部队计划使用高科技激光枪：
在第$i$行安装激光枪可消灭该行所有伞兵，成本为$r_i$。
在第$j$列安装激光枪可消灭该列所有伞兵，成本为$c_j$。
总成本为所有激光枪成本的乘积（例如安装行枪$r_1$和列枪$c_1$，总成本为$r_1 \times c_1$）。

你的任务是选择最经济的激光枪组合，确保消灭所有伞兵且总成本最小。

输入格式

第一行：测试用例数量$T$。
每个测试用例：
三个整数$m$（行数）、$n$（列数）、$l$（伞兵数量）。
$m$个实数$r_i$（行枪成本）。
$n$个实数$c_j$（列枪成本）。
$l$行，每行两个整数表示伞兵的着陆坐标$(x,y)$。

输出格式

对每个测试用例，输出最小总成本，保留四位小数。

样例输入 1

1
4 4 5
2.0 7.0 5.0 2.0
1.5 2.0 2.0 8.0
1 1
2 2
3 3
4 4
1 4

样例输出 1

16.0000

样例解释

伞兵坐标：$(1,1)$、$(2,2)$、$(3,3)$、$(4,4)$、$(1,4)$。
最优方案：选择行枪$r_1=2.0$（覆盖第1行伞兵）、行枪$r_4=2.0$（覆盖第4行伞兵）、列枪$c_2=2.0$（覆盖第2列伞兵）、列枪$c_3=2.0$（覆盖第3列伞兵）。
总成本：$2.0 \times 2.0 \times 2.0 \times 2.0 = 16.0000$。

关键思路

$1$. 问题建模：转化为集合覆盖问题，需选择最便宜的行列组合覆盖所有伞兵。
$2$. 贪心策略：优先选择成本低的行或列，逐步覆盖未被消灭的伞兵。
$3$. 成本计算：由于总成本为乘积形式，需动态维护前最优组合。

来源

Amirkabir University of Technology Local Contest $2006$