题目描述

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

输入格式

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

$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}$ 以下であれば正解として扱われる。

题目大意

高橋君有 $N$ 瓶糖水，青木君有 $M$ 瓶糖水。

高橋君的第 $i$ 瓶糖水有 $A_i$ 份糖 $B_i$ 份水。

青木君的第 $i$ 瓶糖水有 $C_i$ 份糖 $D_i$ 份水。

将两人的糖水各选一瓶混合有 $NM$ 种可能，求其中浓度第 $k$ 大的糖水浓度是多少。

有 $x$ 份糖和 $y$ 份水的糖水浓度是 $\dfrac{100x}{x+y}\%$。

3 1 1
1 2
4 1
1 4
1 4

50.000000000000000

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

提示

制約

• $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$
• 入力される値はすべて整数

Sample Explanation 1

以下では高橋君が持っている $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\ \%$ です。