CF1187G.Gang Up

The leader of some very secretive organization has decided to invite all other members to a meeting. All members of the organization live in the same town which can be represented as $n$ crossroads connected by $m$ two-directional streets. The meeting will be held in the leader's house near the crossroad $1$. There are $k$ members of the organization invited to the meeting; $i$-th of them lives near the crossroad $a_i$.

All members of the organization receive the message about the meeting at the same moment and start moving to the location where the meeting is held. In the beginning of each minute each person is located at some crossroad. He or she can either wait a minute at this crossroad, or spend a minute to walk from the current crossroad along some street to another crossroad (obviously, it is possible to start walking along the street only if it begins or ends at the current crossroad). In the beginning of the first minute each person is at the crossroad where he or she lives. As soon as a person reaches the crossroad number $1$, he or she immediately comes to the leader's house and attends the meeting.

Obviously, the leader wants all other members of the organization to come up as early as possible. But, since the organization is very secretive, the leader does not want to attract much attention. Let's denote the discontent of the leader as follows

• initially the discontent is $0$;
• whenever a person reaches the crossroad number $1$, the discontent of the leader increases by $c \cdot x$, where $c$ is some fixed constant, and $x$ is the number of minutes it took the person to reach the crossroad number $1$;
• whenever $x$ members of the organization walk along the same street at the same moment in the same direction, $dx^2$ is added to the discontent, where $d$ is some fixed constant. This is not cumulative: for example, if two persons are walking along the same street in the same direction at the same moment, then $4d$ is added to the discontent, not $5d$.

Before sending a message about the meeting, the leader can tell each member of the organization which path they should choose and where they should wait. Help the leader to establish a plan for every member of the organization so they all reach the crossroad $1$, and the discontent is minimized.

某个极为隐秘组织的领导者决定邀请所有其他成员参加一次会议。该组织的所有成员均居住在同一座城镇中，该城镇可建模为 $n$ 个路口（crossroad）与 $m$ 条双向街道（street）构成的图。会议将在位于路口 $1$ 附近的领导者住所举行。共有 $k$ 名组织成员被邀请参会；其中第 $i$ 位成员居住在路口 $a_i$ 附近。

所有成员在同一时刻收到会议通知，并立即开始向会议地点移动。每分钟初，每个人均位于某个路口。在每一分钟内，此人可选择：

• 在当前路口等待一分钟；或
• 花费一分钟沿某条街道从当前路口步行至另一路口（显然，仅当该街道以当前路口为端点时，才允许沿其步行）。

在第一分钟初，每位成员均位于其住所所在的路口。一旦某人抵达路口 $1$，他/她即刻进入领导者住所并参加会议。

显然，领导者希望其余所有成员尽可能早地到达。但鉴于该组织高度隐秘，领导者又不希望引起过多注意。我们定义领导者的“不满值”（discontent）如下：

• 初始不满值为 $0$；
• 每当一人抵达路口 $1$，不满值增加 $c \cdot x$，其中 $c$ 是某个固定常数，$x$ 是该人抵达路口 $1$ 所花费的分钟数；
• 每当有 $x$ 名组织成员在同一时刻、沿同一街道、朝同一方向行走时，不满值增加 $d x^2$，其中 $d$ 是某个固定常数。此项不叠加：例如，若两人在同一时刻沿同一街道朝同一方向行走，则不满值增加 $4d$，而非 $5d$。

在发送会议通知前，领导者可为每位成员指定其应选择的路径以及应在何处等待。请帮助领导者为每位成员制定计划，使得所有人最终均能抵达路口 $1$，且总不满值最小化。

The first line of the input contains five integer numbers $n$, $m$, $k$, $c$ and $d$ ($2 \le n \le 50$, $n - 1 \le m \le 50$, $1 \le k, c, d \le 50$) — the number of crossroads, the number of streets, the number of persons invited to the meeting and the constants affecting the discontent, respectively.

The second line contains $k$ numbers $a_1$, $a_2$, ..., $a_k$ ($2 \le a_i \le n$) — the crossroads where the members of the organization live.

Then $m$ lines follow, each denoting a bidirectional street. Each line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) denoting a street connecting crossroads $x_i$ and $y_i$. There may be multiple streets connecting the same pair of crossroads.

It is guaranteed that every crossroad can be reached from every other crossroad using the given streets.

输入的第一行包含五个整数 $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$ 的一条街道。同一对路口之间可能存在多条街道。

保证通过给定的街道，任意两个路口之间均可相互到达。

Print one integer: the minimum discontent of the leader after everyone reaches crossroad $1$.

输出一个整数：所有人到达十字路口 $1$ 后，领导者的最小不满值。

The best course of action in the first test is the following:

• the first person goes along the street $2$ to the crossroad $2$, then goes along the street $1$ to the crossroad $1$ and attends the meeting;
• the second person waits one minute on the crossroad $3$, then goes along the street $2$ to the crossroad $2$, then goes along the street $1$ to the crossroad $1$ and attends the meeting;
• the third person waits two minutes on the crossroad $3$, then goes along the street $2$ to the crossroad $2$, then goes along the street $1$ to the crossroad $1$ and attends the meeting;
• the fourth person waits three minutes on the crossroad $3$, then goes along the street $2$ to the crossroad $2$, then goes along the street $1$ to the crossroad $1$ and attends the meeting.

第一次测试中的最优行动方案如下：

• 第一个人沿街道 $2$ 前往十字路口 $2$，再沿街道 $1$ 前往十字路口 $1$ 并参加会议；
• 第二个人在十字路口 $3$ 等待一分钟，然后沿街道 $2$ 前往十字路口 $2$，再沿街道 $1$ 前往十字路口 $1$ 并参加会议；
• 第三个人在十字路口 $3$ 等待两分钟，然后沿街道 $2$ 前往十字路口 $2$，再沿街道 $1$ 前往十字路口 $1$ 并参加会议；
• 第四个人在十字路口 $3$ 等待三分钟，然后沿街道 $2$ 前往十字路口 $2$，再沿街道 $1$ 前往十字路口 $1$ 并参加会议。