Lazy Walks
Two friends are so mindful of their energy that they calculated the amount of energy they spend by walking from one location to another. So, one friend knows that they’ll spend
A energy to move from one location to a neighbor location, while the second friend will spend B energy for that. Yet, there is a trick they can do. If both of them are at the same location, one can carry the other one and spend
C energy instead of A+B if they both walked to the next location. It's worth noting that the value of C is not necessarily always smaller than A+B, meaning that carrying the other person might not always be the more energy-efficient option.The first friend starts at location 1, while the second friend starts at location 2. They need to get to the location
n and spend as little energy as possible. Can you help them decide the smallest amount of total energy necessary for them to get to the location n.Input
The first line of the input contains 3 integers
A, B, and C (1 ≤ A, B, C ≤ 50 000).The next line contains 2 integers
n and e (1 ≤ n, e ≤ 100 000) the number of locations, and the number of connections.The next
e lines contain the connections between locations represented with a pair of integers Output
The program should print the minimum total energy required for them to get to the
n-th location.Examples
Input | Output |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Explanation
Friend 1: 1 → 4 ⇒ 4
Friend 2: 2 → 3 → 4 ⇒ 8
Together: 4 → 7 → 8 ⇒ 10
In total: 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB