409062: GYM103428 H city safety

Country X is a prosperous free-trade country, which has $$$n$$$ cities connected by $$$n-1$$$ bidirectional roads. Although country X has been very stable, businessmen are generally very sensitive to the safety of cities. They hope country X can strengthen public security forces to ensure the safety of cities.

In addition, businessmen are also concerned about the safety of the surrounding areas. Therefore, if the security force in a city is strengthened, but the security force in the nearby cities are not strengthened, they will still be worried about the threat in nearby cities.

Formally, to strengthen the security force in city $$$i$$$, a cost of $$$w_i$$$ should be paid. Such effort is not in vain, as more businessmen will be attracted and country X will benefit from it. If every city with a distance from city $$$i$$$ less or equal to $$$p$$$ is strengthened, the city $$$i$$$ will gain $$$v_p$$$ more income than before. (if more than one $$$p$$$ satisfy the condition, only the maximum one is considered.)

Now you, as the country's officer, are appointed to deal with this problem. Your goal is to get the maximum benefit (the increased income minus the cost of strengthening the security force).

The first line contains one integer $$$n$$$ ($$$1 \le n \le 200$$$), representing the number of cities in country X.

The second line contains $$$n$$$ integers $$$w_1,w_2,\cdots,w_n$$$ ($$$1 \le w_i \le 10^5$$$), representing the cost of strengthening security force in city $$$i$$$.

The third line contains $$$n$$$ integers $$$v_0,v_1,\cdots,v_{n-1}$$$ ($$$1 \le v_i \le 10^5,\ v_i \le v_{i+1}$$$), representing the benefit as stated above.

Next $$$n-1$$$ lines each contains two integers $$$u,v$$$ ($$$1 \le u,v \le n,\ u\neq v$$$), representing that there is a bidirectional road between city $$$u$$$ and $$$v$$$.

The only line contains an integer, indicating the maximum benefit.

3
2 3 4
1 3 4
1 2
1 3

3