Lucky E

N lucky lancers are defending a tower. Each lancer occupies a position on the tower. Their leader, Lancer C¨2 Chulainn, a hero from the Ulster Cycle of Irish mythology, guards on the top of the tower. We can equalize the tower as a tree, each lancer has a supervisor. After several fierce battles, each lancer is wounded to a certain extent, the lancer with identity i took Ai arrows in his knee. This day, the lancers encounter the most powerful enemy ever -- Gilgamesh. Using his Noble Phantasm, Gate of Babylon, Gilgamesh launched M attacks altogether toward the poor lancers. Each time, Gilgamesh chooses a lancer and attacks. Due to the lancers' Protection from Arrows, this lancer has a probability to avoid this attack. However, if he failed to evade the attack, he and all his subordinates would take an arrow in the knee.

You are given the list of lancers Gilgamesh chose, we consider value S as the value of maximum number of arrows a lancers takes after Gilgamesh attacks.
Now C¨2 Chulainn would like to know the excepted value of S.

The input data will contain several cases(No more than 5). Each case will begin with two numbers N and M, the number of Lancers and the number of Gilgamesh's attacks. Each of the next n-1 lines includes two numbers u and v, meaning that v is u's supervisor.

The next line have N numbers , and the ith number indicates the number of arrows which the ith lancer have had initially in his knee.

The next M line means the attacks of Gilgamesh, include a integer v and a real number p, indicating the v-th lancer will be choose , and he has a probability p that he can't avoid this attack.

N<=100000, M<=3000,
Ai<=10000, 0=<p<=1.0, 1<=v<=N

For each test case, print one line, the excepted value of S. The answer is round to 6 decimal digits.

5 2
2 1
3 1
4 2
5 2
8280 5995 9465 3008 9720
5 0.190
1 0.770

9720.960000

BUPT

2016 Multi-University Training Contest 10