Piggyback Energy Optimization

Bessie and her sister Elsie want to minimize the total energy they spend traveling back to the barn. Bessie spends B units of energy per move, Elsie spends E units of energy per move, and if they travel together (with Bessie carrying Elsie), they spend P units per move.

Bessie starts at field 1, Elsie at field 2, and the barn is located at field n. The farm contains n fields connected by m bidirectional paths. When meeting at an intermediate field i, the total energy cost is given by

$$\text{cost} = d_1[i] \cdot B + d_2[i] \cdot E + d_{barn}[i] \cdot P, $$

where:

• $d_1[i]$ is the minimum number of moves from field 1 to field i,
• $d_2[i]$ is the minimum number of moves from field 2 to field i,
• $d_{barn}[i]$ is the minimum number of moves from field i to the barn (field n).

Your task is to compute the minimum total energy required for both Bessie and Elsie to reach the barn. Note that they may choose a meeting field where they travel separately to it and then move together to the barn, or they may travel completely separately.

inputFormat

The first line contains five integers:
$$B\quad E\quad P\quad n\quad m$$
where B, E, and P are the energy costs per move, n is the number of fields (numbered 1 to n), and m is the number of bidirectional paths.

Each of the next m lines contains two integers u and v indicating that there is a path between fields u and v.

outputFormat

Output a single integer: the minimum total energy required for Bessie and Elsie to reach the barn.

sample

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

20