Gang Up

4000ms

524288K

Description:

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.

Input:

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.

Output:

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

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1187G