Метро

Метрополітен складається з L ліній, на яких розміщені N станцій з номерами від 1 до N. Кожна станція належить одній або більше лініям. Якщо станція належить декільком лініям, то вона є вузловою і на ній можна пересісти на будь-яку лінію, що через неї проходить. Кожна лінія складається з двох або більше станцій та має хоча б одну вузлову. Між будь-якими двома станціями метрополітену існує сполучення, причому вартість проїзду дорівнює мінімальному з двох значень:

1. A копійок нараховується за кожну станцію на шляху слідування, включаючи посадку і висадку;

2. B копійок нараховується за кожну з використаних ліній.

Якої найменшої суми копійок достатньо, щоб дістатися від станції номер i до станції j?

Вхідні дані

У першому рядку записано чотири натуральних числа N, L, A та B. У L наступних рядках записані послідовні номери станцій кожної лінії метро. Останній рядок містить номери i початкової та j кінцевої станцій. Усі числові значення натуральні, L ≤ 10, інші значення не перевищують 100.

Вихідні дані

Мінімальна сума копійок для поїздки.

Приклади