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

Đế chế hùng mạnh nhất

Thời xưa có N đế chế tọa lạc trên một vùng đất xa xăm nọ, chiến đấu tranh giành lẫn nhau. Vua của đế chế hùng mạnh nhất quyết định chinh phục các đế chế khác để tìm kiếm nguồn dầu hỏa! Kho tàng của đế chế này bị hạn chế vì tiền đã được đổ vào chiến dịch tranh cử mới nhất của nhà vua. Kho tàng ban đầu có giá trị là M.

Các đế chế được đánh số từ 1 đến N. Đế chế 1 là đế chế hùng mạnh nhất. Các đế chế được nối với nhau bởi các đường nối hai chiều trong đó chỉ có đúng một đường đi giữa hai đế chế bất kỳ.

Nhà vua thuê bạn để hoạch địch chiến lược cho ông. Các điệp viên của nhà vua cho bạn hai thông số đối với mỗi đất nước i (i>1):

  • Vi = giá trị của nguồn dầu hỏa của nước i
  • Ci = chi phí để chinh phục nước i

Một đế chể chỉ có thể bị chinh phục khi nó kề với đế chế 1 hoặc đế chế 1 đã chinh phục một đế chế kề với nó (nối với nó qua một con đường).

Bạn hãy hoạch địch một chiến lược chinh phục các đế chế khác sao cho tổng giá trị thu được từ nguồn dầu hỏa là lớn nhất. Không được sử dụng quá giới hạn của kho tàng!

Dữ liệu

  • Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 100) và M (0 ≤ M ≤ 2000).
  • Dòng thứ hai chứa N-1 số nguyên V2, V3..., VN (1 ≤ Vi ≤ 100).
  • Dòng thứ ba chứa N-1 số nguyên C2, C3,..., CN (0 ≤ Ci ≤ 30).
  • Mỗi dòng trong N-1 dòng tiếp theo chứa hai số nguyên u, v thể hiện một đường nối.

Kết quả

Một số nguyên duy nhất là tổng giá trị lớn nhất từ nguồn dầu hỏa mà đế chế hùng mạnh nhất có thể thu được bằng việc chinh phục các nước khác.

Ví dụ

Dữ liệu
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

Kết quả
62

Dữ liệu
3 1
1 1
1 0
1 2
2 3

Kết quả
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.