e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Метро

Метро

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

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

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

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
7 3 10 20
2 1 3
6 1 4 5
5 7
2 7
Output example #1
50

Example description: Оплата за посещённые станции будет 5x10=50 коп., а за использованные линии 3x20=60 коп.

Source Stage III All-Ukrainian School Olympiad 2011-2012, Round 1, Zhytomyr