Description

There are $N$ factories connected by $N - 1$ roads, and any two factories are reachable. Each factory has a production value and a pollution value. Now we plan to demolish $M$ factories so that the remaining factories still form a single connected component and the value of total production divided by total pollution is maximized.

Input Format

The first line contains two integers $N, M$ representing the number of factories and the number to demolish.

The second line contains $N$ positive integers $w_i$, representing the production of each factory.

The third line contains $N$ positive integers $c_i$, representing the pollution of each factory.

Then follow $N - 1$ lines. Each line contains two positive integers $a, b$ ($1 \le a, b \le N$) indicating that $a$ and $b$ are connected.

Output Format

Output the maximum value of total production divided by total pollution, rounded to one decimal place.

3 2
2 3 4
1 1 1
1 2
2 3

4.0

Hint

Constraints

For all testdata, $1 < N < 100$, $1 \le M < N$, $1 \le w_i \le 10000$, and $1 \le c_i \le 10000$.

Translated by ChatGPT 5