Lazy Walks

Zwei Freunde achten sehr auf ihren Energieverbrauch und haben berechnet, wie viel Energie sie jeweils beim Gehen von einem Ort zum nächsten verbrauchen. Einer der beiden benötigt dafür A Energie, während der andere B Energie aufwendet.

Allerdings gibt es einen Trick: Wenn sich beide am selben Ort befinden, kann einer den anderen tragen und dabei C Energie verbrauchen, anstatt dass jeder für sich läuft und zusammen A + B aufwenden würde. Es ist wichtig zu beachten, dass C nicht unbedingt immer kleiner als A + B ist. Das bedeutet, dass das Tragen des anderen nicht in jedem Fall die energieeffizientere Option darstellt.

Der erste Freund startet an Ort 1, während der zweite Freund an Ort 2 beginnt. Beide sollen den Ort n erreichen und dabei insgesamt möglichst wenig Energie verbrauchen. Kannst du helfen, die minimale Gesamtenergiemenge zu ermitteln, die notwendig ist, damit beide den Ort n erreichen?

Eingabe

Die erste Zeile der Eingabe enthält 3 ganze Zahlen A, B und C (1 ≤ A, B, C ≤ 50 000).

Die nächste Zeile enthält 2 ganze Zahlen n und e (1 ≤ n, e ≤ 100 000), also die Anzahl der Orte und die Anzahl der Verbindungen.

Die darauffolgenden e Zeilen enthalten die Verbindungen zwischen den Orten. Jede Verbindung wird durch ein Paar ganzzahliger Werte und (1 ≤ ≤ n) beschrieben, die bedeuten, dass die beiden Orte direkt miteinander verbunden sind.

Ausgabe

Das Programm soll die minimal erforderliche Gesamtenergiemenge ausgeben, damit beide den n-ten Ort erreichen können.

Beispiele

Erklärung

Freund 1: 1 → 4 ⇒ 4

Freund 2: 2 → 3 → 4 ⇒ 8

Zusammen: 4 → 7 → 8 ⇒ 10

Insgesamt: 4 + 8 + 10 = 22