AT_kupc2018_k 光と闇の調和

现在你面前有 $N$ 个光之宝珠和 $M$ 个暗之宝珠。 每个光之宝珠的能量分别为 $a_1, a_2, \ldots, a_N$，对应的，每个暗之宝珠的能量为 $b_1, b_2, \ldots, b_M$。 对于每个光之宝珠 $i$（$1 \leq i \leq N$），它与暗之宝珠的结合范围是从第 $l_i$ 个到第 $r_i$ 个（即 $l_i \leq j \leq r_i$）。 你的任务是为这些宝珠设定等级，等级范围为 $1$ 到 $K$ 的整数。 设定等级后，每个宝珠只会与等级比自己低或相同的宝珠结合，那么仅与比自己等级高的宝珠结合的宝珠就会消失。 请你求出，在这种设定下，剩余宝珠的能量平均值的最大值。

输入以以下格式从标准输入给出： > $N$ $M$ $K$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_M$ $l_1$ $r_1$ $l_2$ $r_2$ $\ldots$ $l_N$ $r_N$

请输出剩余宝珠能量平均值的最大值。允许的绝对误差或相对误差应不超过 $10^{-5}$。

### 约束条件 - 所有输入为整数。 - $1 \leq N, M \leq 3 \times 10^4$ - $2 \leq K \leq 3 \times 10^4$ - $1 \leq a_i, b_i \leq 10^5$ - $1 \leq l_i \leq r_i \leq M$ - 每个宝珠至少结合一个其他的宝珠。 ### 部分分 - 当 $N, M, K \leq 300$ 时，正确解答可获得 $30$ 分。 - 对于没有额外约束的数据集，正确解答可获得另外的 $370$ 分。 ### 样例说明 例如，如果设定光之宝珠的等级为 $10$ 和 $8$，暗之宝珠的等级为 $7, 9, 9$，那么第 $2$ 个光之宝珠与第 $1$ 个暗之宝珠会消失。此时，剩下的宝珠能量平均值是 $(15 + 12 + 13) / 3 = 13.3333...$，这已是最大值。 **本翻译由 AI 自动生成**