Submit | All submissions | Best solutions | Back to list |
KINGDOM - The mightiest kingdom |
English | Vietnamese |
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):
- Vi = the value of this country's oil sources
- Ci = 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 V2, V3..., VN (1 ≤ Vi ≤ 100).
- The third line contains N-1 integers C2, C3,..., CN (0 ≤ Ci ≤ 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
Added by: | VOJ Team |
Date: | 2008-09-03 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET |
Resource: | VNOI Marathon '08 - Round 12/DivA Probem Setter: Sharif Shah Newaj Bhuiyan |