Trong một vương quốc có ~N~ vùng, được đánh số từ ~1~ đến ~N~, vùng được đánh số ~1~ là kinh đô của vương quốc. Có đúng ~N-1~ con đường nối trực tiếp giữa các vùng với nhau đảm bảo mỗi vùng đều có thể tới kinh đô thông qua các con đường này. Vương quốc thực hiện phương cách quản lý phân cấp từ kinh đô tới các vùng bên dưới. Cụ thể, vùng ~X~ được gọi là quản lý vùng ~Y~ nếu mọi cách di chuyển thông qua các con đường từ vùng ~Y~ tới kinh đô đều luôn đi qua vùng ~X~.

Các vùng đều có các thửa ruộng có thể canh tác lương thực trên đó, vùng thứ ~i~ ~(1\le i \le N)~ có ~Q_i~ thửa ruộng, mỗi thửa ruộng nếu canh tác dự kiến sẽ cho sản lượng đúng ~W_i~ tấn. Nhà vua mong muốn tổng sản lượng lương thực trên toàn vương quốc phải đạt tối thiểu ~S~ tấn, biết rằng:

• Do đặc thù mỗi vùng, vùng thứ ~i~ nếu sử dụng ~K_i~ thửa ruộng để canh tác lương thực sẽ tốn tổng chi phí canh tác và bảo vệ mùa màng là ~K_i^2\times C_i~.

• Nếu vùng ~X~ không sử dụng thửa ruộng nào để canh tác lương thực thì tất cả các vùng mà ~X~ quản lý cũng đều không canh tác lương thực.

Yêu cầu: Hãy giúp nhà vua xác định dãy ~(K_1,K_2,...,K_N)~ là số lượng thửa ruộng tương ứng được phân công canh tác cho từng vùng, sao cho tổng chi phí canh tác và bảo vệ mùa màng là nhỏ nhất mà vẫn đạt được sản lượng mong muốn của nhà vua, hoặc thông báo là không có cách phân công nào thỏa mãn.

Dữ liệu

Vào từ văn bản FOOD.INP:

• Dòng đầu ghi hai số nguyên dương ~N~ và ~S~ ~(N,S\le 5000)~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo ghi ba số nguyên dương ~Q_i,W_i~ và ~C_i~ ~(Q_i,W_i\le 5000;C_i\le10^6)~.

• Mỗi dòng trong ~N-1~ dòng tiếp theo ghi hai số nguyên dương ~u~ và ~v~ ~(1\le u,v \le N)~ thể hiện có con đường nối trực tiếp giữa hai vùng ~u~ và ~v~.

Các số trên cùng một dòng cách nhau bởi dấu cách

Kết quả

Ghi ra file văn bản FOOD.OUT một số nguyên duy nhất là tổng chi phí canh tác và bảo vệ mùa màng nhỏ nhất tìm được. Ghi ra ~-1~ nếu không có phương án phân công nào thỏa mãn.

Ràng buộc

• Có ~16\%~ số test ứng với ~16\%~ số điểm thỏa mãn: ~Q_i=1,\forall i=1,2,...,N~ và có các con đường trực tiếp từ kinh đô đến tất cả các vùng khác.

• ~14\%~ số test khác ứng với ~14\%~ số điểm thỏa mãn: ~N,S\le 500~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~Q_i=W_i=1,\forall i=1,2,...,N~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~Q_i=1,\forall i=1,2,...,N~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: Có các con đường trực tiếp từ kinh đô đến tất cả các vùng khác.

• ~14\%~ số test còn lại ứng với ~14\%~ số điểm không có ràng buộc gì thêm.

Ví dụ

Input

6 9
2 1 5
4 3 1
1 3 2
1 2 4
1 1 10
1 7 1
1 2
2 3
2 4
1 5
5 6

Output

11

Giải thích

Dãy ~(K_1,K_2,K_3,K_4,K_5,K_6)=(1,2,1,0,0,0)~ cho tổng sản lượng lương thực là:

~1 \times 1 + 2 \times 3 + 1 \times 3 + 0 \times 2 + 0 \times 1 + 0 \times 7 = 10 \ge 9~,

và là dãy cho chi phí nhỏ nhất cần tìm bằng: ~1^2 \times 5 + 2^2 \times 1 + 1^2 \times 2 + 0^2 \times 4 + 0^2 \times 10 + 0^2 \times 1 = 11~.