URI Online Judge | 2789

Water Crisis

By Dâmi Henrique BR Brazil

Timelimit: 3

Montes Claros, a city in the north of Minas Gerais, has been undergoing a major water crisis in recent times. Scarcity of water has affected the lives of many residents, making them put their homes up for sale at a price well below the market. Abbade, a major investor, sees this crisis moment as an investment opportunity and intends to buy several of these houses.

There are N houses in Montes Claros and M of them are for sale. A curious fact is that there is only one way between any pair of houses and it is possible, from any house, to reach all the others in the city.

Because of the crisis, Q-water trucks pass monthly through the city streets. The i-th of these trucks makes the way from a certain home Xi to another Yi home, leaving Li gallons of water in each house on its way.

Abbade has D reais to invest in the purchase of houses. However, since he fears that the crisis will get worse and real estate will never be resold, he will buy the houses so that the sum of the amount of water received by the trucks in those houses is as large as possible. To decide which houses to buy, he asked for his help.


The first line contains two N and D integers separated by space, representing the number of houses in the city and the money that Abbade owns for the purchase of the houses. Each house is identified by an integer between 1 and N. Follow N-1 lines. The i-th of them will contain two integers, Ai and Bi, meaning that there is a direct route
between these houses.

The next line will contain an integer M, indicating the number of homes that are for sale. Follow M lines. The i-th of them will contain two integers Ci and Vi, where Ci is the number of one of the houses and Vi its selling price. It is guaranteed that a house will not appear more than once.

The next line will contain an integer Q, indicating the number of water trucks that will pass through the city. Follow the Q lines. The i-th of these lines will contain three integers Xi, Yi and Li, indicating that the i-th truck will depart from house Xi to house Yi leaving Li liters of water in each of the houses along the way.

1 ≤ N ≤ 5 × 103

1 ≤ D ≤ 103

1 ≤ MN

1 ≤ Vi ≤ 100

1 ≤ Q ≤ 5 × 105

1 ≤ L ≤ 103


Write in the output a line containing an integer: as much water as the houses Abbade will buy will receive, since he will buy houses in order to maximize that value.

Input Sample Output Sample

6 10
1 2
1 3
3 4
3 5
3 6
1 8
4 3
6 5
2 6 3
4 6 5
1 2 7