eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Метро

Метро

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
prb2795

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
7 3 10 20
2 1 3
6 1 4 5
5 7
2 7
Вихідні дані #1
50
Автор Сергій Матвійчук
Джерело III етап Всеукраїнської олімпіади школярів 2011-2012, 1 тур, м. Житомир