Factory Demolition Optimization

You are given a connected tree of N factories (nodes) and N − 1 roads (edges) connecting them such that any two factories are reachable. Each factory i has an associated production value P_i and a pollution value Q_i.

You must demolish exactly M factories. After demolition, the remaining factories (exactly N − M nodes) must still form a connected tree. Your task is to choose which M factories to remove so that the ratio \[ \frac{\text{Total Production}}{\text{Total Pollution}} = \frac{\sum P_i}{\sum Q_i} \] of the remaining factories is maximized. Output the maximum achievable ratio with 6 decimal places of precision.

Note: It is guaranteed that all pollution values are positive.

inputFormat

The first line contains two integers N and M separated by a space, where N (1 ≤ N ≤ 100) is the number of factories and M (0 ≤ M < N) is the number of factories to demolish.

The second line contains N integers, where the i-th integer is P_i, the production value of factory i.

The third line contains N integers, where the i-th integer is Q_i, the pollution value of factory i.

Each of the next N − 1 lines contains two integers u and v (1-indexed) indicating there is a bidirectional road between factories u and v.

outputFormat

Output the maximum achievable value of \(\frac{\text{Total Production}}{\text{Total Pollution}}\) among all valid connected subtrees with exactly N − M factories. Print the answer rounded to 6 decimal places.

sample

3 1
10 20 30
2 4 5
1 2
2 3

5.555556