题目描述

有 $n$ 份溶液 A 和 $m$ 份溶液 B。第 $i$ 份溶液 A 含有 $x_i$ 克粉和 $y_i$ 克水，第 $j$ 份溶液 B 含有 $a_j$ 克粉和 $b_j$ 克水。

选择一份溶液 A 和一份溶液 B 混合，得到的新溶液浓度为 $\dfrac{x_i + a_j}{x_i + y_i + a_j + b_j}$。

共有 $n \times m$ 种混合方案。求所有混合方案中浓度第 $k$ 大的值，以百分比形式输出（即值域为 $[0, 100]$）。

注意：粉量和水量的取值保证不会出现分母为零的情况。

输入格式

第一行三个整数 $n, m, k$，分别表示溶液 A 的数量、溶液 B 的数量和目标排名。

接下来 $n$ 行，每行两个整数 $x_i, y_i$，表示第 $i$ 份溶液 A 的粉量和水量。

接下来 $m$ 行，每行两个整数 $a_j, b_j$，表示第 $j$ 份溶液 B 的粉量和水量。

输出格式

输出一行一个实数，表示第 $k$ 大的浓度百分比。你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$ 即视为正确。

样例

3 1 1
1 2
4 1
1 4
1 4

50.00000000

2 2 2
3 1
3 3
3 1
3 3

60.00000000

2 2 3
1 0
4 0
0 1
1 1

66.66666667

样例解释

对于样例 1：有三份溶液 A：$(1,2),(4,1),(1,4)$，一份溶液 B：$(1,4)$。

• 混合 A1 和 B1：浓度 $= (1+1)/(1+2+1+4) = 2/8 = 25\%$
• 混合 A2 和 B1：浓度 $= (4+1)/(4+1+1+4) = 5/10 = 50\%$
• 混合 A3 和 B1：浓度 $= (1+1)/(1+4+1+4) = 2/10 = 20\%$

第 1 大的浓度为 $50\%$。

对于样例 2：溶液 A：$(3,1),(3,3)$，溶液 B：$(3,1),(3,3)$。四种混合的浓度分别为 $75\%, 60\%, 60\%, 50\%$，第 $2$ 大的浓度为 $60\%$。

对于样例 3：溶液 A：$(1,0),(4,0)$，溶液 B：$(0,1),(1,1)$。四种混合的浓度分别为 $83.33\dots\%, 80\%, 66.67\dots\%, 50\%$，第 $3$ 大的浓度为 $200/3 \approx 66.67\%$。

数据范围与约定

对于所有数据，$1 \le n, m \le 10^5$，$1 \le k \le \min(10^9, n \times m)$，$0 \le x_i, y_i, a_j, b_j \le 10^5$，且对于任意 $i$，$x_i + y_i > 0$；对于任意 $j$，$a_j + b_j > 0$。

下发样例

[下发样例下载](file://sample.zip)