Metro

Metropoliten L xətdən ibarətdir və bu xətlərdə 1-dən N-ə qədər nömrələnmiş N stansiya yerləşir. Hər bir stansiya bir və ya daha çox xəttə aiddir. Əgər stansiya bir neçə xəttə aiddirsə, o, qovşaq stansiyasıdır və onun vasitəsilə keçən istənilən xəttə keçmək mümkündür. Hər bir xətt iki və ya daha çox stansiyadan ibarətdir və ən azı bir qovşaq stansiyasına malikdir. Metropolitenin istənilən iki stansiyası arasında əlaqə mövcuddur və gediş haqqı iki dəyərdən minimumuna bərabərdir:

1. Hər bir stansiya üçün, o cümlədən minmə və düşmə üçün A qəpik hesablanır;

2. İstifadə olunan hər bir xətt üçün B qəpik hesablanır.

i nömrəli stansiyadan j nömrəli stansiyaya çatmaq üçün ən azı nə qədər qəpik lazımdır?

Giriş məlumatları

Birinci sətirdə dörd təbii ədəd N, L, A və B yazılmışdır. Sonrakı L sətirdə hər bir metro xəttinin ardıcıl stansiya nömrələri yazılmışdır. Sonuncu sətir başlanğıc i və son j stansiyalarının nömrələrini ehtiva edir. Bütün ədədi dəyərlər təbiidir, L ≤ 10, digər dəyərlər 100-ü keçmir.

Çıxış məlumatları

Səyahət üçün minimal qəpik məbləği.

Nümunələr