InterCity
Ukraynanın dəmiryolu sistemi bir neçə il əvvəl olduqca rahat idi. İstənilən iki şəhər arasında birbaşa qatar mövcud idi (bu, "tək tərəfli" demək deyil). İstənilən yerə çatmaq üçün sadəcə B UAH ödəmək kifayət idi.
Lakin son zamanlarda Ukraynada böyük dəyişikliklər baş verdi. Çoxlu yeni qatarlar istifadəyə verildi. Hər yeni qatar köhnələrdən birini əvəz etdi və onun qiyməti A UAH oldu. Beləliklə, hər bir şəhər cütlüyü arasında hələ də birbaşa qatar (yeni və ya köhnə) işləyir. Hər bir qatar hər iki istiqamətdə işləyir və qiyməti istiqamətdən asılı deyil.
Ukraynada N böyük şəhər var və siz 1 nömrəli şəhərdə yaşayırsınız. Məqsədiniz N nömrəli şəhərə ən ucuz marşrutla çatmaqdır, köçürmələrin sayından asılı olmayaraq.
Giriş verilənləri
Birinci sətir dörd tam ədəd N, K, A və B (2 ≤ N ≤ 500000, 0 ≤ K ≤ 500000, 1 ≤ A, B ≤ 500000) - şəhərlərin sayı, yeni qatarların sayı, yeni və köhnə gediş haqqı. Sonra K sətir gəlir. Hər biri iki tam ədəd u_i və v_i (1 ≤ u_i, v_i ≤ N) ehtiva edir, bu da u_i və v_i şəhərləri arasında yeni qatarın istifadəyə verildiyini göstərir. Məlumdur ki, u_i və v_i eyni deyil. Hər bir şəhər cütlüyü bir dəfədən çox təkrarlanmır.
Çıxış verilənləri
1 nömrəli şəhərdən N nömrəli şəhərə çatmaq üçün ən ucuz yolun qiymətini göstərən bir tam ədəd P çıxarın.