配点 : $500$ 点

問題文

高橋君は $N$ 本の砂糖水を、青木君は $M$ 本の砂糖水を持っています。 高橋君の持っている $i$ 番目の砂糖水は砂糖 $A_i$ グラムと水 $B_i$ グラムからなります。 青木君の持っている $i$ 番目の砂糖水は砂糖 $C_i$ グラムと水 $D_i$ グラムからなります。 2 人の持つ砂糖水をそれぞれ 1 本ずつ選んで混ぜる方法は $NM$ 通りあります。そのような方法でできる砂糖水の中で、濃度が高い方から $K$ 番目の砂糖水の濃度が何 $\%$ であるかを求めてください。 ここで、砂糖 $x$ グラムと水 $y$ グラムからなる砂糖水の濃度は $\dfrac{100x}{x+y}\ \%$ です。また、砂糖が溶け残ることは考えないものとします。

制約

• $1 \leq N, M \leq 5 \times 10^4$
• $1 \leq K \leq N \times M$
• $1 \leq A_i, B_i, C_i, D_i \leq 10^5$
• 入力される値はすべて整数

入力

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

$N$ $M$ $K$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

$C_1$ $D_1$

$C_2$ $D_2$

$\vdots$

$C_M$ $D_M$

出力

濃度が高い方から $K$ 番目の砂糖水の濃度をパーセントで出力せよ。 なお、真の値との絶対誤差または相対誤差が $10^{-9}$ 以下であれば正解として扱われる。

3 1 1
1 2
4 1
1 4
1 4

50.000000000000000

以下では高橋君が持っている $i$ 番目の砂糖水と青木君が持っている $j$ 番目の砂糖水を混ぜてできる砂糖水を $(i, j)$ と表します。 あり得る砂糖水の混ぜ方とその濃度を列挙すると以下のようになります。

• $(1, 1)$ : $100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \%$
• $(2, 1)$ : $100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \%$
• $(3, 1)$ : $100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \%$

この中で濃度が高い方から $1$ 番目の砂糖水は $(2, 1)$ で、濃度は $50 \%$ です。

2 2 2
6 4
10 1
5 8
9 6

62.500000000000000

4 5 10
5 4
1 6
7 4
9 8
2 2
5 6
6 7
5 3
8 1

54.166666666666664