Taxi sharing

Several employees of a company worked overtime and finished late at night. $K$ of them ($2 \le K \le 15$) normally take public transport, and they ask the manager to have their taxi fare reimbursed. Taxis are plentiful, so the manager could order one taxi per employee. That is far too expensive. A taxi carries 1 to 4 passengers, and a shared ride for people who live close to each other costs much less. At the same time, the manager decided it would be rude to make an employee wait outdoors while the driver takes a colleague home and comes back. So the manager wants the cheapest way to get everybody home under these rules.

• The $K$ employees are split into groups of 1, 2, 3 or 4 people. The manager decides the grouping.
• Employees of the same group ride the same taxi.
• The group leaves the company and drives to the home of one of its members, who gets out there. If anybody is left, the taxi drives to the next person's home, and so on. The manager also decides whose home comes first, whose comes second, and so on.
• The manager is not one of the $K$ employees and belongs to no group. He drives his own car and takes no employee with him.

The company and the employees' homes sit at vertices of a weighted graph. Most edges are undirected (two-way roads), but some may be directed (one-way). The weight of an edge is the fare of travelling along it by taxi. The graph is strongly connected, so a path runs from every vertex to every other vertex. A taxi fare is a distance fare plus a boarding fee. The boarding fee is charged once per car, no matter the distance covered or the number of passengers.

The first line contains the number of vertices $N$ ($5 \le N \le 20000$) and the number of edges $M$ ($N \le M \le 50000$).

Each of the next $M$ lines contains four integers. The first is 1 or 2, where 1 means a one-way road and 2 means a two-way road. The next two, $u$ and $v$ ($u \ne v$, $1 \le u \le N$, $1 \le v \le N$), are the vertices the road connects; a one-way road runs from $u$ to $v$. The fourth is the fare of travelling along that road by taxi, between 5 and 5000.

The next line contains the boarding fee, an integer between 500 and 50000.

The next line contains the index of the vertex where the company is located, between 1 and $N$.

The next line contains the number of employees $K$ ($2 \le K \le 15$).

The last line contains $K$ indices of the vertices where the employees live, each between 1 and $N$. Two employees may live at the same vertex, but nobody lives at the vertex where the company is located.

Print the minimal total cost of taking all employees home, on one line.

In the first example the minimal cost 4500 is reached when one taxi takes all four employees and drives to the 2nd employee's home, then the 1st employee's, then the 4th employee's, then the 3rd employee's. In the second example the minimal cost 3700 is reached with two taxis. One drives to the 1st employee's home and then to the 2nd employee's, the other drives to the 3rd employee's home and then to the 4th employee's.