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

Метро

Метро

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Метрополитен состоит из L линий, на которых розмещены N станций с номерами от 1 до N. Каждая станция принадлежит одной или больше линиям. Если станция принадлежит нескольким линиям, то она является узловой и на ней можно пересесть на любую другую линию, проходящую через неё. Каждая линия состоит из двух или более станций и имеет хотя бы одну узловую. Между любыми двумя станциями метрополитена существует сообщение, причём стоимость проезда равна минимальному из двух значений:

  1. A копеек насчитывается за каждую станцию на пути следования, включая посадку и высадку;

  2. B копеек насчитывается за каждую из использованных линий.

Какая минимальная сумма в копейках достаточна, чтобы добраться от станции номер i до станции j?

Входные данные

В первой строке записаны четыре натуральных числа N, L, A и B. В L последующих строках записаны последовательные номера станций каждой линии метро. Последняя строка содержит номера i начальной и j конечной станции. Все числовые значения натуральны, L10, другие значения не превышают 100.

Выходные данные

Минимальная сумма в копейках для поездки.

Пример

Входные данные #1
7 3 10 20
2 1 3
6 1 4 5
5 7
2 7
Выходные данные #1
50
Источник III этап Всеукраинской олимпиады школьников 2011-2012, 1 тур, Житомир