Giải bài trực tuyến

Once upon a time, there were N kingdoms in a far far away land, fighting with each other. King of the mightiest kingdom decided to conquer other kingdoms, looking for oil sources! The kingdom's budget is a bit limited because the money were pumped into the king's latest election campaign. The budget is initially M.

The kingdoms are numbered from 1 to N. Kingdom 1 is the mightiest. The kingdoms are connected by bidirectional roads in which there is exactly once path between any two kingdoms.

The king hired you to make a strategic plan for him. His spies gave you two numbers for each country i (i>1):

• V_i = the value of this country's oil sources
• C_i = the cost of conquering this country

A kingdom can be conquered only when it is adjacent to kingdom 1 or when you've conquered an adjacent kingdom to it (which is connected to it via a road).

Now, your task is to make a plan to conquer other kingdoms so that the total value from oil sources is maximized. Never exceed the budget!

Input

• The first line contains two integers N (1 ≤ N ≤ 100) and M (0 ≤ M ≤ 2000).
• The second line contains N-1 integers V₂, V₃..., V_N (1 ≤ V_i ≤ 100).
• The third line contains N-1 integers C₂, C₃,..., C_N (0 ≤ C_i ≤ 30).
• Each line in the next N-1 lines contains two integers u, v representing a road.

Output

A single integer that is the maximum value of oil sources the Mightiest King can get from conquering other countries.

Example

Input
10 3
10 10 10 9 5 8 8 7 10
0 0 0 0 0 3 2 2 0
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
8 10



Output
62

Input
3 1
1 1
1 0
1 2
2 3

Output
2