시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 512 MB111100.000%

문제

Note that $0$-based indexing is used throughout the problem.

You are given an array $a$ of length $n$ and $k$ non-empty sets of integers from $0$ to $n-1$. Let $S_p$ denote the $p$-th set. Each integer from $0$ to $n-1$ belongs to exactly one of those sets. It is guaranteed that $0$ belongs to $S_0$.

You choose a \uline{nonincreasing} array $c$ of nonnegative reals. $c_0$ must be positive. Let $d_p$ denote $\sum_{i \in S_p} c_i a_i$. Let $X$ denote $\frac{\min_{p=1}^{k-1} d_p}{d_0}$. What is the maximum value of $X$ you can obtain by choosing $c$ accordingly?

입력

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 4 \cdot 10^4, 2 \leq k \leq 4$), the length of $a$ and the number of sets. 

The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^9$), the elements of $a$.

The third line contains $n$ integers $b_i$ ($b_0 = 0, 0 \leq b_i < k$) meaning that $i$ belongs to $S_{b_i}$.

All sets $S_p$ are non-empty. In other words, all integers from $0$ to $k-1$ occur at least once among $b_i$.

출력

Print a single integer --- the maximum value of $X$ you can obtain accurate to absolute or relative error of at most $10^{-4}$.

예제 입력 1

4 4
1 1 1 1
0 1 2 3

예제 출력 1

1

예제 입력 2

3 3
3 2 2
0 1 2

예제 출력 2

0.66666666666666666668

예제 입력 3

5 4
3 2 1 2 5
0 1 3 0 2

예제 출력 3

0.29411764686215561816