AT_abc294_f [ABC294F] Sugar Water 2

高桥君有 $N$ 瓶砂糖水，青木君有 $M$ 瓶砂糖水。 高桥君的第 $i$ 瓶砂糖水由 $A_i$ 克砂糖和 $B_i$ 克水组成。 青木君的第 $i$ 瓶砂糖水由 $C_i$ 克砂糖和 $D_i$ 克水组成。 两人各自选一瓶砂糖水混合，共有 $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}$，则视为正确。

## 限制条件 - $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$ - 输入的所有数值均为整数 ## 样例解释 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\%$ 在这些混合方式中，浓度最高的是 $(2, 1)$，其浓度为 $50\%$。 由 ChatGPT 4.1 翻译