AT_kupc2018_k 光と闇の調和

[problemUrl]: https://atcoder.jp/contests/kupc2018/tasks/kupc2018_k $ N $ 個の光オーブと $ M $ 個の闇オーブがあります。 $ i $ 番目の光オーブのエネルギーは $ a_i $ で、$ i $ 番目の闇オーブのエネルギーは $ b_i $ です。 また、各 $ i\ \in\ \{1,\ 2,\ ...,\ N\},\ j\ \in\ \{l_i,\ l_i+1,\ ...,\ r_i\} $ について、$ i $ 番目の光オーブと $ j $ 番目の闇オーブは結合されています。 あなたは、各オーブに $ 1 $ 以上 $ K $ 以下の整数で表されるレベルを同時に設定します。 レベルを設定した直後に、自分のレベルよりも高いレベルのオーブとしか結合されていないオーブが全て消滅します。 残ったオーブのエネルギーの平均値の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ b_2 $ $ ... $ $ b_M $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ : $ $ 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 $ - どのオーブも1つ以上のオーブと結合されている。 ### 部分点 - $ N,\ M,\ K\ \leq\ 300 $ を満たすデータセットに正解した場合は、$ 30 $ 点が与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 370 $ 点が与えられる。 ### Sample Explanation 1 例えば、次のように設定すれば、$ 2 $ 番目の光オーブと $ 1 $ 番目の闇オーブが消滅し、残ったオーブのエネルギーの平均値は $ (15\ +\ 12\ +\ 13)\ /\ 3\ =\ 13.3333... $ となり最大です。 - 光オーブのレベル: $ 10,\ 8 $ - 闇オーブのレベル: $ 7,\ 9,\ 9 $