eolymp
bolt
Try our new interface for solving problems
Problems

Метро

Метро

Time limit 1 second
Memory limit 64 MiB

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

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

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

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

Input data

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

Output data

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

Examples

Input example #1
7 3 10 20
2 1 3
6 1 4 5
5 7
2 7
Output example #1
50
Source Stage III All-Ukrainian School Olympiad 2011-2012, Round 1, Zhytomyr