23704번 - Basirovich Maxim 스페셜 저지다국어

문제

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

제한

힌트