Sau khi dẫn cô gái ấy đi trên đoạn đường "biết hát" kia, _minhduc đã nhận được cảm tình của cô ấy. Tuy nhiên, ở đây, shiba lại đang rất "lụy" người yêu cũ, vì vậy đã tới lúc để _minhduc chơi đùa một chút...

shiba có một vườn hoa nho nhỏ. Cậu ấy quyết định sẽ trồng hoa để tặng hoa cho cô "người yêu cũ" kia để tỏ lòng thành. Khu vườn gồm \(N\) bồn hoa, được đánh số từ \(1\) đến \(N\), trong đó một số bồn hoa được kết nối bằng ống nước. Các bồn hoa và các ống nước tạo thành một cây, trong đó các bồn hoa là các nút và các ống nước là các cạnh. Mỗi bồn hoa có một máy bơm được lắp đặt có thể bơm nước từ dưới đất lên trên. Nước này sẽ được tưới cho bồn hoa mà máy bơm đó đặt và nó sẽ chảy qua các ống nước đến một số bồn hoa khác mà có đường ống kết nối đến chúng.

Các máy bơm được đánh số từ \(1\) đến \(N\) (số máy bơm bằng với số bồn hoa trong khu vườn). Nếu máy bơm đặt trong một bồn hoa có số thứ tự \(x\) (\(1 \le x \le N)\) hoạt động trong \(p\) phút, nước sẽ đến tất cả các bồn hoa có khoảng cách không quá \(p-1\) cạnh từ \(x\) trong cây (khoảng cách giữa hai đỉnh \(u\) và \(v\) bất kì là số cạnh \(u\) cần đi qua để đến tới \(v\)).

Hệ thống máy bơm được thiết kế sao cho một máy bơm chạy trước, sau đó là máy bơm khác và cứ tiếp tục như vậy (hai máy bơm không bao giờ hoạt động đồng thời, và một máy bơm chỉ có thể chạy một lần). Một bồn hoa được coi là đã được tưới nước nếu có nước đã tưới cho nó, không quan tâm nước đó là từ máy bơm nào. Các máy bơm được thiết kế sao cho nếu một máy bơm có số thứ tự \(i\) chạy, nó chỉ được chạy tối đa \(t_i\) phút. Một lần chạy của máy bơm phải kéo dài một số phút nguyên.

Tất cả các máy bơm đều tiêu thụ điện như sau:

• Một lần chạy trong \(1\) phút tốn \(c_1\) VND, \(2\) phút chạy tốn \(c_2\) VND và cứ tiếp tục như vậy. Nếu máy bơm không chạy, nó sẽ không tiêu thụ điện.

shiba cần tính được số tiền tối thiểu cần chi trả cho điện năng sao cho một bộ máy bơm phù hợp chạy để tất cả các bồn hoa đều được tưới. Tuy nhiên, do mải trồng hoa và cũng do quá đau buồn, cậu ấy quyết định nhờ cậy tới "người anh em" _minhduc của mình. ~Do rủ lòng thương~ nên _minhduc quyết định giúp, thế nhưng chiếc Macbook M2 Pro của cậu ấy vẫn chưa được sửa xong. Bạn hãy giúp cậu ấy nhé.

Yêu cầu: Xác định số tiền tối thiểu sao cho một bộ máy bơm phù hợp chạy, để tất cả các bồn hoa đều có thể được tưới.

Input

• Dòng đầu tiên chứa số nguyên dương \(\phi\) - số thứ tự của subtask chứa test đó \((1 \le \phi \le 7)\).

• Dòng thứ hai chứa số nguyên dương \(N\) \((1 \le N \le 2000)\) - số bồn hoa, cũng là số máy bơm.

• Dòng thứ ba chứa \(N\) số nguyên \(c_1,c_2,...,c_N\) (\(0 \le c_i \le 10^6)\) - số tiền điện năng mà một máy bơm chạy trong \(1,2,...,N\) phút.

• Dòng thứ tư chứa \(N\) số nguyên \(t_1,t_2,...,t_N\) (\(0 \le t_i \le N)\) - thời gian chạy tối đa cho mỗi máy bơm. Trong trường hợp \(t_i = 0\) thì máy bơm thứ \(i\) không sử dụng được.

• \(N-1\) dòng cuối cùng mỗi dòng chứa hai số \(u,v\) mô tả ống nước (cạnh) nối bồn hoa có số \(u\) và \(v\). Bộ dữ liệu đảm bảo rằng các bồn hoa và các ống nước nối với nhau tạo thành cây.

• Dữ liệu vào luôn đảm bảo rằng \(c_1 \le c_2 \le ... \le c_N\).

Output

• In ra số tiền tối thiểu thỏa mãn yêu cầu đề bài, nếu không có cách chọn thỏa mãn thì in ra \(-1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 8\).

• Subtask \(2\) (\(10\%\) số điểm): Có \(N \le 75\) và cây có dạng đường thẳng.

• Subtask \(3\) (\(10\%\) số điểm): Có \(N \le 500\) và cây có dạng đường thẳng.

• Subtask \(4\) (\(15\%\) số điểm): Có \(N \le 2000\) và cây có dạng đường thẳng.

• Subtask \(5\) (\(15\%\) số điểm): Có \(N \le 75\).

• Subtask \(6\) (\(15\%\) số điểm): Có \(N \le 500\).

• Subtask \(7\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

 1
 8
 1 2 5 7 8 14 20 29
 2 4 1 0 2 3 2 0
 2 5
 6 5
 5 7
 2 3
 1 8
 4 1
 1 5

5

2
8
1 2 4 8 10 12 24 26
1 4 3 8 2 5 6 0
8 7
5 4
2 3
2 1
7 6
5 6
4 3

6