Cõng Bạn

Có $N$ địa điểm và $M$ con đường hai chiều giữa chúng. Bessie xuất phát từ địa điểm $1$, Elsie xuất phát từ địa điểm $2$, cả hai cần đến địa điểm $N$.

• Khi di chuyển một mình, Bessie tốn $B$ năng lượng mỗi bước, Elsie tốn $E$ năng lượng mỗi bước.
• Khi di chuyển cùng nhau (cõng nhau), cả hai tốn $P$ năng lượng mỗi bước (tổng cộng).

Chúng có thể gặp nhau tại bất kỳ địa điểm nào, rồi di chuyển cùng nhau về đích. Tìm tổng năng lượng tối thiểu để cả hai đến địa điểm $N$.

Dữ liệu vào

Dòng đầu chứa năm số nguyên $B$, $E$, $P$, $N$, $M$.

• $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$, $v$ — một con đường giữa địa điểm $u$ và $v$.

Dữ liệu ra

Một số nguyên duy nhất — tổng năng lượng tối thiểu.

Ràng buộc

• $1\le B,E,P,N,M\le 40000$
• $N\ge 3$
• Luôn tồn tại đường đi từ địa điểm $1$ và $2$ đến $N$

Ví dụ