请注意，本题中所有数组和集合的索引均从 $0$ 开始。

给你一个长度为 $n$ 的数组 $a$ 和 $k$ 个由 $0$ 到 $n - 1$ 的整数组成的非空集合。记 $S_p$ 为第 $p$ 个集合。每个 $0$ 到 $n - 1$ 的整数恰好属于这些集合中的一个。保证 $0$ 属于 $S_0$。

你需要选择一个非递增的非负实数数组 $c$。$c_0$ 必须为正数。记 $d_p = \sum_{i \in S_p} c_i a_i$。记 $X = \frac{\min_{p=1}^{k-1} d_p}{d_0}$。通过合理选择 $c$，你能得到的 $X$ 的最大值是多少？

输入格式

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 4 \cdot 10^4$，$2 \le k \le 4$），分别表示 $a$ 的长度和集合的数量。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示 $a$ 的元素。

第三行包含 $n$ 个整数 $b_i$（$b_0 = 0$，$0 \le b_i < k$），表示 $i$ 属于 $S_{b_i}$。

所有集合 $S_p$ 都是非空的。换句话说，所有 $0$ 到 $k - 1$ 的整数在 $b_i$ 中至少出现一次。

输出格式

输出一个数，表示你能得到的 $X$ 的最大值。与标准答案的绝对误差或相对误差不超过 $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