← 返回题目列表

AtCoder · past201912_m

M. 自动选择

中文机器翻译题面 查看原题

警告

在日本标准时间 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

这次我们有强大的辅助怪物,应该使用一只。