M - おまかせ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

注意

この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

あなたはソーシャルゲームを運営している。このゲームには多数のモンスターが登場し、各モンスターは質量と魔力の二つのパラメータを持つ。

あるユーザは N 体のモンスターを所持し、i 体目の所持モンスター (1 \leqq i \leqq N) の質量は A_i、魔力は B_i である。

また、これと別に M 体のお助けモンスターがおり、i 体目のお助けモンスター (1 \leqq i \leqq M) の質量は C_i、魔力は D_i である。

ユーザは、これらの N + M 体のモンスターからちょうど 5 体を選び、それらを合成することができる。ただし、お助けモンスターは 1 体までしか選べない。ここで、合成後のモンスターの強さを (使用されたモンスターの魔力の和) / (使用されたモンスターの質量の和) と定義する。

あなたは、合成後のモンスターの強さが最大になるように自動でモンスターを選ぶ機能を実装したい。一度だけ合成を行うとき、合成後のモンスターの強さの最大値を求めるプログラムを作成せよ。

制約

  • 5 \leqq N \leqq 1,000
  • 1 \leqq M \leqq 100
  • 1 \leqq A_i, B_i \leqq 100,000
  • 1 \leqq C_i, D_i \leqq 100,000
  • 入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
:
A_N B_N
C_1 D_1
C_2 D_2
:
C_M D_M

出力

合成後のモンスターの強さの最大値を表す実数を出力せよ。ジャッジの出力との絶対誤差または相対誤差が 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,2,4,5,6 番目の所持モンスターを選ぶのが最適である。

入力例 2

6 2
1 20
1 3
32 100
1 1
1 2
2 5
10 100
96 874

出力例 2

9.0000000000000

今回は強力なお助けモンスターがおり、1 体使うべきである。

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You run a social game, which features many monsters. Each monster has two parameters: Mass and Magic Power (MP).

A user owns N monsters. The Mass and MP of the i-th monster owned (1 \leq i \leq N) are A_i and B_i, respectively.

Additionally, there are M helper monsters. The Mass and MP of the i-th helper monster (1 \leq i \leq M) are C_i and D_i, respectively.

The user can choose exactly five out of these N + M monsters and combine them into one new monster. However, among those five monsters, there should be at most one helper monster. Let us define the strength of the new monster as the sum of the MPs of the monsters used, divided by the sum of the Masses of the monsters used.

You want to implement a function that automatically chooses monsters to combine so that the strength of the new monster is maximized. Write a program to find the maximum possible strength of the new monster when combining monsters only once.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print a real number representing the maximum possible strength of the new monster. Your output is considered correct if the absolute or relative error from the judge's output is at most 10^{-6}.

Sample Input 1

6 2
10 30
20 60
10 10
30 100
50 140
40 120
10 3
30 1

Sample Output 1

3.0000000000000

It is optimal to do without the helper monsters and choose the 1-st, 2-nd, 4-th, 5-th, and 6-th monsters owned.

Sample Input 2

6 2
1 20
1 3
32 100
1 1
1 2
2 5
10 100
96 874

Sample Output 2

9.0000000000000

We have powerful helper monsters this time and should use one.