糖水 2

题目描述

高桥和青木分别有 $N$ 瓶和 $M$ 瓶糖水。

高桥的第 $i$ 瓶糖水由 $A_i$ 克糖和 $B_i$ 克水组成。

青木的第 $i$ 瓶糖水由 $C_i$ 克糖和 $D_i$ 克水组成。

从高桥的糖水中选一瓶、青木的糖水中选一瓶进行混合，共有 $NM$ 种选法。在这样得到的 $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}$ 即视为正确。

样例

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 \%$

其中糖浓度最高的是 $(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

数据范围

• $1 \le N, M \le 5 \times 10^4$
• $1 \le K \le N \times M$
• $1 \le A_i, B_i, C_i, D_i \le 10^5$
• 输入中的所有值均为整数