Bessie và cô em Elsie gặm cỏ ở những cánh đồng khác nhau vào ban ngày, còn buổi tối cả hai đều muốn đi bộ về chuồng để nghỉ ngơi. Là những cô bò thông minh, họ nghĩ ra một kế hoạch nhằm giảm thiểu tổng năng lượng cả hai tiêu hao khi di chuyển.

Bessie tiêu hao \(B\) đơn vị năng lượng khi đi từ một cánh đồng sang một cánh đồng kề bên, còn Elsie tiêu hao \(E\) đơn vị năng lượng khi đi sang một cánh đồng kề bên. Tuy nhiên, nếu Bessie và Elsie ở cùng một cánh đồng, Bessie có thể cõng Elsie trên vai và cả hai cùng di chuyển sang một cánh đồng kề bên mà chỉ tiêu hao \(P\) đơn vị năng lượng (trong đó \(P\) có thể nhỏ hơn đáng kể so với \(B+E\), lượng năng lượng Bessie và Elsie sẽ tiêu hao nếu tự đi riêng sang cánh đồng kề bên). Nếu \(P\) rất nhỏ, phương án tiết kiệm năng lượng nhất có thể là Bessie và Elsie đi đến một cánh đồng chung để gặp nhau, rồi cùng di chuyển theo kiểu cõng nhau trong phần còn lại của hành trình đến chuồng. Tất nhiên, nếu \(P\) lớn, việc Bessie và Elsie đi riêng vẫn có thể hợp lý nhất. Nhân tiện, cả Bessie và Elsie đều không hài lòng với thuật ngữ “piggyback”, vì họ không hiểu tại sao những chú lợn trong trang trại lại đáng được ghi hết công lao cho hình thức di chuyển tuyệt vời này.

Cho \(B\), \(E\), \(P\) cùng với sơ đồ trang trại, hãy tính lượng năng lượng nhỏ nhất cần thiết để Bessie và Elsie đến được chuồng.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên dương \(B\), \(E\), \(P\), \(N\) và \(M\). Tất cả các số này đều không vượt quá \(40\,000\). \(B\), \(E\) và \(P\) có ý nghĩa như mô tả ở trên. \(N\) là số cánh đồng trong trang trại (được đánh số từ 1 đến \(N\), với \(N \ge 3\)), còn \(M\) là số đường nối giữa các cánh đồng. Bessie và Elsie lần lượt xuất phát ở cánh đồng 1 và 2. Chuồng nằm ở cánh đồng \(N\).

\(M\) dòng tiếp theo, mỗi dòng mô tả một đường nối giữa một cặp cánh đồng khác nhau bằng hai số nguyên là chỉ số của hai cánh đồng. Các đường nối đều đi được theo hai chiều. Luôn có thể đi từ cánh đồng 1 đến cánh đồng \(N\), cũng như từ cánh đồng 2 đến cánh đồng \(N\), qua một chuỗi các đường nối như vậy.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng năng lượng nhỏ nhất mà Bessie và Elsie cần tiêu hao để đến chuồng.

Ví dụ

4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8

22

Nguồn

USACO 2014 December Contest, Silver — Piggyback. Tác giả đề: Brian Dean, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=491