K - 光と闇の調和

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

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 以下の整数で表されるレベルを同時に設定します。

レベルを設定した直後に、自分のレベルよりも高いレベルのオーブとしか結合されていないオーブが全て消滅します。

残ったオーブのエネルギーの平均値の最大値を求めてください。

制約

  • 入力は全て整数である。
  • 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 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

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

2 3 10
15 10
11 12 13
1 2
2 3

出力例 1

13.3333333333

例えば、次のように設定すれば、2 番目の光オーブと 1 番目の闇オーブが消滅し、残ったオーブのエネルギーの平均値は (15 + 12 + 13) / 3 = 13.3333... となり最大です。

  • 光オーブのレベル: 10, 8
  • 闇オーブのレベル: 7, 9, 9

入力例 2

1 1 2
10
20
1 1

出力例 2

20.0000000000

入力例 3

10 10 5
97925 72167 60717 63438 89200 6986 16104 76483 23620 9806
24712 38409 16480 2643 28121 51951 23492 4420 28197 28607
1 2
3 10
2 5
9 9
6 7
2 8
3 5
2 3
4 10
5 9

出力例 3

51672.4545454545