提示: 欢迎访问OurACM平台。
Problem 2069 Factories

Accept: 45    Submit: 287
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There are N factories, and N-1 roads connect them, every factory can reach all the other factories. a factory has a Output value and a Pollution value.

Now kk want to remove M factories, a factory was removed the roads connect it will be removed also. After remove M factories, kk want every remain factory can reach all the other remain factories.

We define O1 equal the sum of the remain factories's Output value, P1 equal the sum of the remain factories's Pollution value. Government want the O1/P1 Maximum.

Can you tell kk the Maximum value of O1/P1.

Input

There are multiple tests.

Each test first line contain one integer numbers N M(1<N<100, 1<=M<N), N factories and M factories need be removed.

Second line contain N integers, is the Output value of every factory.

Third line contain N integers, is the Pollution values of every factory.

Next N-1 lines each line contain two integers a b(1<=a,b<=N), that mean a and b are connect.we guarantee every factory can reach all the other factories.

Output

Output the Maximum value of O1/P1.

Sample Input

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

Sample Output

4.0

Source

FOJ有奖月赛-2011年12月

Submit  Back  Status  Discuss