Minimizing the Ratio on a Tree Path

Given a tree with (n) nodes. Each node (i) has two weights (a_i) and (b_i). Your task is to find a simple path containing exactly (m) nodes such that the ratio (\frac{\sum a_i}{\sum b_i}) is minimized. If no such path exists, output (-1).

inputFormat

The first line contains two space‐separated integers (n) and (m).\nThe second line contains (n) integers representing (a_1, a_2, \ldots, a_n).\nThe third line contains (n) integers representing (b_1, b_2, \ldots, b_n).\nEach of the following (n-1) lines contains two integers (u) and (v), denoting an edge between nodes (u) and (v).

outputFormat

If a valid path exists, print the minimal ratio, formatted to 6 decimal places. Otherwise, print (-1).

sample

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

0.750000