Hanaa và Sherine đang chơi Willow, một trò chơi trên một bảng gồm \(N\) thành phố. Thành phố thứ \(i\) chứa \(C_i\) đồng xu, và có \(N - 1\) con đường hai chiều chạy giữa các thành phố. Tất cả các thành phố đều có thể đi đến được với nhau. Trò chơi diễn ra như sau:

Đầu tiên, Hanaa chọn một trong các thành phố làm vị trí bắt đầu của mình, sau đó Sherine chọn một trong các thành phố (có thể trùng với thành phố Hanaa đã chọn) làm vị trí bắt đầu của mình. Sau đó, họ luân phiên thực hiện lượt chơi, Hanaa là người đi trước.

Trong lượt của một người chơi, người đó phải lấy tất cả các đồng xu tại thành phố mà họ đang đứng, nếu có; có thể không có đồng xu nào nếu thành phố ban đầu không có đồng xu, hoặc nếu một trong hai người chơi đã bắt đầu một lượt tại thành phố đó trước đó. Sau đó, nếu có thể, người chơi phải di chuyển đến một thành phố lân cận thông qua một con đường. Có thể không di chuyển được vì mỗi con đường chỉ được sử dụng tối đa một lần. Điều này có nghĩa là sau khi một người chơi đã sử dụng một con đường, không ai được phép sử dụng lại con đường đó nữa. Trò chơi kết thúc khi cả Hanaa và Sherine đều không thể thực hiện nước đi.

Sau khi trò chơi kết thúc, điểm của mỗi người chơi bằng hiệu số giữa số đồng xu người đó có và số đồng xu của đối thủ. Nếu đối thủ có nhiều đồng xu hơn, điểm của người đó sẽ là số âm. Cả hai người chơi đều cố gắng tối đa hóa điểm số của mình. Giả sử cả hai đều sử dụng chiến thuật tối ưu nhất để tối đa hóa điểm số, hãy tìm điểm số cao nhất mà Hanaa có thể đạt được.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\), số lượng thành phố trên bảng. \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên \(C_i\), số lượng đồng xu trong thành phố \(i\).

Cuối cùng sẽ có thêm \(N - 1\) dòng, dòng thứ \(i\) (\(i\) bắt đầu từ 1) chứa một số nguyên duy nhất \(j\) (\(i < j \le N\)) cho biết có một con đường giữa thành phố \(i\) và thành phố \(j\). Tất cả các thành phố được đảm bảo có thể đi đến được với nhau khi bắt đầu trò chơi.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là điểm số cao nhất mà Hanaa có thể đạt được.

Ràng buộc

• \(1 \le T \le 50\).
• \(0 \le C_i \le 10000\).

Phân nhóm

• Small dataset: \(2 \le N \le 80\).
• Large dataset: \(2 \le N \le 500\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3
1000
200
1000
2
3
8
8
0
8
0
0
0
0
10
2
5
4
5
6
7
8
10
150
200
0
5000
0
100
0
0
0
10000
10
3
8
5
8
7
8
9
10

Case #1: 200
Case #2: -2
Case #3: 5100

Nguồn

Google Code Jam 2014, Vòng 3, bài Willow.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.