怠け者の散歩 (Lazy Walks)

2人の友人は、移動時に消費するエネルギーについてとても慎重に計算しています。1人目の友人が隣の場所へ移動するときには A のエネルギーを消費し、2人目の友人は隣の場所へ移動するときに B のエネルギーを消費します。

ところが、2人が同じ場所にいるときには、どちらかがもう片方を運ぶことができ、その場合は2人分の移動を合わせて A + B ではなく C のエネルギーで済ませることができます。ただし C は必ずしも A + B より小さいとは限らないため、運んだほうが常に得とは限りません。

1人目の友人は場所1から出発し、2人目の友人は場所2から出発します。2人とも場所 n に到達し、しかも合計エネルギーの消費を最小に抑えたいと考えています。2人が場所 n へ到達するために必要なエネルギーの合計の最小値を求めてください。

入力

最初の行には、3つの整数 A、B、C が与えられます (1 ≤ A, B, C ≤ 50 000)。

次の行には、2つの整数 n と e (1 ≤ n, e ≤ 100 000) が与えられます。n は場所の数、e は接続の数です。

続く e 行には、各行に と が書かれており、これは場所 と場所 が直接つながっていることを意味します (1 ≤ ≤ n)。

出力

2人が場所 n に到達するのに必要なエネルギー合計の最小値を出力してください。

例

解説

友人1: 1 → 4 ⇒ 4

友人2: 2 → 3 → 4 ⇒ 8

2人一緒: 4 → 7 → 8 ⇒ 10

合計: 4 + 8 + 10 = 22