Caminhadas Preguiçosas

Dois amigos estão tão atentos ao gasto de energia que calcularam quanto consomem ao caminhar de uma localização para outra. Assim, um deles sabe que gasta A unidades de energia para ir de uma localização até uma localização vizinha, enquanto o outro gasta B unidades de energia para fazer o mesmo trajeto.

No entanto, há um truque que eles podem usar. Se ambos estiverem na mesma localização, um pode carregar o outro e gastar C unidades de energia, em vez de A + B, caso ambos andassem individualmente até a próxima localização. É importante ressaltar que C não é necessariamente menor que A + B, portanto, carregar o outro nem sempre será a opção mais econômica em termos de energia.

O primeiro amigo começa na localização 1, enquanto o segundo começa na localização 2. Eles precisam chegar até a localização n gastando o mínimo de energia possível. Consegue ajudá-los a determinar qual é a menor quantidade total de energia necessária para ambos chegarem à localização n?

Entrada

A primeira linha da entrada contém 3 inteiros A, B e C (1 ≤ A, B, C ≤ 50 000).

A linha seguinte contém 2 inteiros n e e (1 ≤ n, e ≤ 100 000), que representam o número de localizações e o número de conexões.

As próximas e linhas descrevem as conexões entre as localizações, cada uma representada por um par de inteiros e (1 ≤ ≤ n), indicando que há uma ligação entre as duas localizações correspondentes.

Saída

O programa deve imprimir a quantidade mínima de energia total necessária para que ambos cheguem à localização n.

Exemplos

Explicação

Amigo 1: 1 → 4 ⇒ 4

Amigo 2: 2 → 3 → 4 ⇒ 8

Juntos: 4 → 7 → 8 ⇒ 10

Total: 4 + 8 + 10 = 22