G. Сходка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Глава одной очень секретной организации решил собрать всех участников организации на встречу. Все они живут в одном и том же городе, который можно рассматривать как $$$n$$$ перекрестков, соединенных $$$m$$$ улицами. По улицам можно перемещаться в обоих направлениях. Встреча пройдет в доме главы около перекрестка $$$1$$$. На встречу, помимо главы, приглашены $$$k$$$ человек, состоящих в организации; $$$i$$$-й из них живет у перекрестка $$$a_i$$$.

Все приглашенные одновременно получат приглашение и начнут движение к месту встречи. В начале каждой минуты каждый человек находится на каком-то перекрестке. Он или она может подождать минуту на этом перекрестке, или за минуту пройти по улице до другого перекрестка (очевидно, можно идти только по тем улицам, на одном из концов которой стоит человек). В начале первой минуты каждый человек находится на перекрестке, около которого живет. Как только человек достигает перекрестка $$$1$$$, он или она сразу же приходит в дом главы организации.

Очевидно, глава хочет, чтобы все пришли как можно раньше. Но так как организация очень секретная, глава не хочет, чтобы движение ее участников привлекло слишком много внимания. Определим недовольство главы следующим образом:

  • в самом начале недовольство равно $$$0$$$;
  • когда участник встречи приходит к перекрестку $$$1$$$, недовольство увеличивается на $$$c \cdot x$$$, где $$$c$$$ — некоторая заданная константа, а $$$x$$$ — количество минут, которое потребовалось человеку, чтобы достичь перекрестка $$$1$$$;
  • когда $$$x$$$ участников организации идут по одной и той же улице в одну и ту же минуту в одном и том же направлении, к недовольству прибавляется $$$dx^2$$$, где $$$d$$$ — некоторая заданная константа. Например, если два человека идут по одной и той же улице в одну и ту же минуту в одном и том же направлении, к недовольству добавляется $$$4d$$$ (не $$$5d$$$).

Перед отправкой сообщения о встрече глава организации может отправить каждому сообщение, каким путем ему надо двигаться и на каких перекрестках ждать. Помогите главе разработать такой план, при котором все достигают перекрестка $$$1$$$, и недовольство минимально возможно.

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

Первая строка содержит пять чисел $$$n$$$, $$$m$$$, $$$k$$$, $$$c$$$ и $$$d$$$ ($$$2 \le n \le 50$$$, $$$n - 1 \le m \le 50$$$, $$$1 \le k, c, d \le 50$$$) — количество перекрестков, количество улиц, количество человек, приглашенных на встречу и константы, влияющие на недовольство соответственно.

Вторая строка содержит $$$k$$$ чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$2 \le a_i \le n$$$) — перекрестки, на которых живут члены организации.

Затем следует $$$m$$$ строк, каждая содержит описание двунаправленной улицы. Каждая строка содержит два числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) обозначающая улицу, соединяющую перекрестки $$$x_i$$$ и $$$y_i$$$. Может быть несколько улиц, соединяющих одинаковые пары перекрестков.

Гарантируется, что от любого перекрестка можно добраться до любого другого, используя заданные дороги.

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

Выведите одно целое число — минимальное недовольство главы организации после того, как все придут к перекрестку $$$1$$$.

Примеры
Входные данные
3 2 4 2 3
3 3 3 3
1 2
2 3
Выходные данные
52
Входные данные
3 3 4 2 3
3 2 2 3
1 2
2 3
2 3
Выходные данные
38
Примечание

Лучший план действий в первом примере — следующий:

  • первый человек идет по улице $$$2$$$ к перекрестку $$$2$$$, затем идет по улице $$$1$$$ к перекрестку $$$1$$$ и приходит на встречу;
  • второй человек ждет минуту на перекрестке $$$3$$$, затем идет по улице $$$2$$$ к перекрестку $$$2$$$, затем идет по улице $$$1$$$ к перекрестку $$$1$$$ и приходит на встречу;
  • третий человек ждет две минуты на перекрестке $$$3$$$, затем идет по улице $$$2$$$ к перекрестку $$$2$$$, затем идет по улице $$$1$$$ к перекрестку $$$1$$$ и приходит на встречу;
  • четвертый человек ждет три минуты на перекрестке $$$3$$$, затем идет по улице $$$2$$$ к перекрестку $$$2$$$, затем идет по улице $$$1$$$ к перекрестку $$$1$$$ и приходит на встречу;