Problem Description

There are $ N $ light orbs and $ M $ dark orbs.

The energy of the $ i $ -th light orb is $ a_i $ , and the energy of the $ i $ -th dark orb is $ b_i $ .

Also, for each $i \in \{1, 2, ..., N\}, j \in \{l_i, l_i+1, ..., r_i\}$, the $ i $ -th light orb and the $ j $ -th dark orb are combined.

You will simultaneously set levels for each orb, represented by integers between $ 1 $ and $ K $ inclusive.

Immediately after setting the levels, all orbs that are only combined with orbs of higher levels will vanish.

Find the maximum average value of the energy of the remaining orbs.

Input Format

The input is given from the standard input in the following format:

$ 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 $

Output Format

Output the maximum average value of the energy of the remaining orbs. The answer will be considered correct if the absolute or relative error is at most $ 10^{-5} $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

13.3333333333

Sample Input #2

1 1 2
10
20
1 1

Sample Output #2

20.0000000000

Sample Input #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

Sample Output #3

51672.4545454545

Notes/Hints

Constraints

• All inputs are integers.
• $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$
• Each orb is combined with at least one other orb.

Partial Points

• If you solve the dataset where $N, M, K \leq 300$, you will be awarded $ 30 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 370 $ points.

Sample Explanation 1

For example, by setting the levels as follows, the $ 2 $ -nd light orb and the $ 1 $ -st dark orb will vanish, and the average value of the remaining orbs' energy will be $ (15 + 12 + 13) / 3 = 13.3333... $, which is the maximum.
- Levels of light orbs: $ 10, 8 $
- Levels of dark orbs: $ 7, 9, 9 $

见题面 Input 部分

见题面 Output 部分