問題文

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 点が与えられる。

入力例 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