Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KINGDOM - The mightiest kingdom

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

Được gửi lên bởi:VOJ Team
Ngày:2008-09-03
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:VNOI Marathon '08 - Round 12/DivA
Probem Setter: Sharif Shah Newaj Bhuiyan

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.