警告
在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。
问题陈述
您运行一款社交游戏,其中有许多怪物。每个怪物都有两个参数:质量和魔力(MP)。
用户拥有 N 怪物。弥撒和国会议员 i拥有的第个怪物 (1 \leq i \leq N) 是 A_i 和 B_i。
此外,还有 M 辅助怪物。弥撒和国会议员 i第-个辅助怪兽 (1 \leq i \leq M) 是 C_i 和 D_i。
用户可以从其中选择五个 N + M 怪物并将它们组合成一只新怪物。不过,那五只怪物中,最多应该有一只辅助怪物。让我们将新怪物的强度定义为所使用怪物的 MP 总和除以所使用怪物的质量总和。
您想要实现一个自动选择怪物进行组合的功能,以使新怪物的强度最大化。编写一个程序,找出仅组合一次怪物时新怪物的最大可能强度。
约束
- 5 \leq N \leq 1000
- 1 \leq M \leq 100
- 1 \leq A_i, B_i \leq 100000
- 1 \leq C_i, D_i \leq 100000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 : A_N B_N C_1 D_1 C_2 D_2 : C_N D_N
输出
打印一个代表新怪物最大可能强度的实数。如果法官输出的绝对或相对误差最多为,则您的输出被认为是正确的 10^{-6}.
示例输入 1
6 2 10 30 20 60 10 10 30 100 50 140 40 120 10 3 30 1
示例输出 1
3.0000000000000
最好不要使用辅助怪物并选择 1-st, 2-nd, 4-th, 5-th,以及 6拥有的第 只怪物。
示例输入 2
6 2 1 20 1 3 32 100 1 1 1 2 2 5 10 100 96 874
示例输出 2
9.0000000000000
这次我们有强大的辅助怪物,应该使用一只。