Sau khi đánh thức sức mạnh của Dynamite Belial, Bell Daizora tiến vào trận chiến cuối cùng trong Beyblade Burst QuadDrive.

Trước mặt Bell là Tháp Vô Cực, gồm \(N\) tầng và được mô hình hóa dưới dạng một cây có gốc tại tầng \(1\). Tầng \(1\) là cổng vào của tòa tháp. Mỗi tầng còn lại đều có đúng một tầng cha.

Tại mỗi tầng \(i\) (\(2\le i\le N\)), một Blader đang chờ đối đầu với Bell. Blader này sở hữu Beyblade có sức mạnh phòng thủ là \(D_i\).

Để vượt qua từng tầng, Bell có thể sử dụng một trong hai chế độ của Dynamite Belial.

Low Mode

• Sức mạnh tấn công: \(A\).
• Tiêu hao \(K_1\) thể lực cho mỗi trận đấu.

Bell chỉ có thể chiến thắng nếu

High Mode

• Sức mạnh tấn công: \(B\).
• Tiêu hao \(K_2\) thể lực cho mỗi trận đấu.

Bell chỉ có thể chiến thắng nếu

Bell bắt đầu tại tầng \(1\) và phải chọn đúng một đường đi đơn từ tầng \(1\) đến một tầng lá.

Một tầng lá là tầng không có tầng con trong cây gốc tại tầng \(1\).

Nếu Bell không đủ sức mạnh để đánh bại Blader tại một tầng thì hành trình trên nhánh đó kết thúc ngay lập tức.

Bell Fire

Giữa hai tầng liên tiếp, Bell có thể giữ nguyên hoặc đổi chế độ chiến đấu.

• Nếu giữ nguyên chế độ, Bell tiêu hao đúng lượng thể lực của chế độ hiện tại.
• Nếu đổi chế độ, kỹ năng Bell Fire được kích hoạt, giúp Belial hồi lại \(R\) thể lực.

Khi đó, lượng thể lực tiêu hao của trận đấu được tính bằng

trong đó:

• \(K=K_1\) nếu Bell chuyển sang Low Mode.
• \(K=K_2\) nếu Bell chuyển sang High Mode.

Yêu cầu

Hãy giúp Bell Daizora tìm một đường đi từ tầng \(1\) đến một tầng lá sao cho:

• Bell chiến thắng tất cả các Blader trên đường đi.
• Tổng lượng thể lực tiêu hao là nhỏ nhất.

Nếu Bell không thể đi tới bất kỳ tầng lá nào, hãy in ra -1.

Input

Dòng đầu tiên chứa sáu số nguyên

Dòng thứ hai chứa \(N-1\) số nguyên

\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên

mô tả một hành lang nối giữa hai tầng \(u\) và \(v\).

Giới hạn

• \(2\le N\le10^5\)
• \(1\le A,B,D_i\le10^9\)
• \(0\le K_1,K_2,R\le10^9\)

Output

In ra một số nguyên duy nhất là tổng thể lực tiêu hao nhỏ nhất.

Nếu không tồn tại đường đi hợp lệ thì in ra

-1

Ví dụ

Input

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

Output

5

Giải thích

Bell chọn đường đi

1 → 2 → 5

• Tại tầng \(2\), Bell sử dụng Low Mode.

Vì

Bell chiến thắng và tiêu hao

thể lực.

• Tại tầng \(5\), Bell chuyển sang High Mode.

Do kích hoạt Bell Fire, Bell được hồi \(R=2\) thể lực.

Lượng thể lực tiêu hao là

Đồng thời

nên Bell tiếp tục chiến thắng.

Tổng thể lực tiêu hao là

Đây là giá trị nhỏ nhất.

Ghi chú

• Bell có thể chuyển chế độ bao nhiêu lần tùy ý.
• Chỉ những lần đổi chế độ mới được hưởng hiệu ứng hồi thể lực của Bell Fire.
• Mỗi Blader chỉ cần đánh bại đúng một lần khi Bell đi qua tầng tương ứng.