Score : $500$ points

问题陈述

高桥和青木分别拥有 $N$ 和 $M$ 瓶糖水。
高桥的第 $i$ 瓶糖水由 $A_i$ 克糖和 $B_i$ 克水组成。
青木的第 $i$ 瓶糖水由 $C_i$ 克糖和 $D_i$ 克水组成。

从高桥和青木的糖水中各选择一瓶进行混合，共有 $NM$ 种不同的方式。在这 $NM$ 种可能得到的糖水中，找出第 $K$ 高浓度的糖水中的糖浓度。

这里，由 $x$ 克糖和 $y$ 克水组成的糖水的糖浓度计算公式为 $\dfrac{100x}{x+y}$ 百分比。我们忽略饱和度的影响。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi and Aoki have $N$ and $M$ bottles of sugar water, respectively.
Takahashi's $i$-th sugar water is composed of $A_i$ grams of sugar and $B_i$ grams of water.
Aoki's $i$-th sugar water is composed of $C_i$ grams of sugar and $D_i$ grams of water.
There are $NM$ ways to choose one from Takahashi's sugar waters and one from Aoki's and mix them. Among the $NM$ sugar waters that can be obtained in this way, find the concentration of sugar in the sugar water with the $K$-th highest concentration of sugar.
Here, the concentration of sugar in sugar water composed of $x$ grams of sugar and $y$ grams of water is $\dfrac{100x}{x+y}$ percent. We will ignore saturation.

Constraints

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

Input

The input is given from Standard Input in the following format:

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

Output

Print the concentration of sugar in the sugar water with the $K$-th highest concentration of sugar in percent.
Your output will be considered correct if the absolute or relative error from the true value is at most $10^{−9}$.

Sample Input 1

3 1 1
1 2
4 1
1 4
1 4

Sample Output 1

50.000000000000000

Let $(i, j)$ denote the sugar water obtained by mixing Takahashi's $i$-th sugar water and Aoki's $j$-th.
Below are the sugar waters that can be obtained and their concentrations of sugar.

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

Among them, the sugar water with the highest concentration of sugar is $(2, 1)$, with a concentration of $50$ percent.

Sample Input 2

2 2 2
6 4
10 1
5 8
9 6

Sample Output 2

62.500000000000000

Sample Input 3

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

Sample Output 3

54.166666666666664

update @ 2024/3/10 12:14:56