公司的一些员工因加班工作到深夜。其中 $K$（$2 \le K \le 15$）名平时乘坐公共交通工具的员工请求公司经理为他们报销出租车费。现在有许多可用的出租车，经理可以为每位员工单独叫一辆出租车。然而，他觉得这样太贵了，因为一辆出租车可以容纳 1 到 4 名乘客，而让住得近的人合乘同一辆出租车会便宜得多。另一方面，经理认为，如果让某些员工在室外等待，而司机先送他们的同事回家再返回来接他们，这样太不礼貌了。因此，经理希望选择一种最便宜的方法将所有员工送回家，并满足以下约束条件：
- 所有 $K$ 名员工被分成若干组，每组包含 1、2、3 或 4 个人；经理决定如何分组。
- 同一组的员工合乘同一辆出租车。
- 同组的所有人首先乘车前往其中一名成员的家，该成员在此下车；组内剩余的人（如果还有的话）继续前往下一位成员的家，依此类推。乘车顺序（谁是第 1 个、谁是第 2 个，等等）也由经理决定。
- 经理本人不是这 $K$ 名员工之一，也不属于任何小组。他自己开车，并且不想与任何员工拼车。
公司 and 员工的家位于一个带权图的顶点上。图中的大多数边是无向的（双向道路），但有些可能是单向的（单向道路）。图中每条边的权重表示乘坐出租车沿该边行驶的费用。该图是强连通的，即从图中的每个顶点到任何其他顶点都存在一条路径。
出租车费用包括里程费 and 起步价。起步价按车收取，与行驶距离和乘客人数无关。
输入格式
第一行包含顶点数 $N$（$5 \le N \le 20000$）和边数 $M$（$N \le M \le 50000$）。
接下来有 $M$ 行，每行包含四个整数：
- 第一个数是 1 或 2，表示单向或双向道路；
- 接下来两个数 $u, v$（$u \neq v, 1 \le v \le N, 1 \le u \le N$）表示连接的顶点（如果道路是单向的，则方向为从 $u$ 到 $v$）；
- 第四个数（范围在 5 到 5000 之间）表示该边的权重（乘坐出租车通过该边的费用）。
下一行包含起步价（范围在 500 到 50000 之间的整数）。
下一行包含公司所在顶点的编号（范围在 1 到 $N$ 之间）。
下一行包含员工人数 $K$（$2 \le K \le 15$）。
最后一行包含 $K$ 个数字（每个数字范围在 1 到 $N$ 之间）—— 员工居住的顶点编号。不同的员工可能住在同一个顶点，但没有人住在公司所在的顶点。
输出格式
输出一个整数 —— 将所有员工送回家所需的最小总费用。
样例
输入样例 1
6 7 2 1 2 200 2 1 3 1000 2 1 4 1200 2 2 3 900 2 6 2 1300 2 6 4 200 2 4 5 100 1000 1 4 2 3 5 6
输出样例 1
4500
输入样例 2
6 7 2 1 2 200 2 1 3 1000 2 1 4 1200 2 2 3 900 2 6 2 1300 2 6 4 200 2 4 5 100 500 1 4 2 3 5 6
输出样例 2
3700
说明
在第一个样例中，当一辆出租车搭载所有 4 名员工并按照以下顺序行驶时，可以达到最小总费用 4500：先到第 2 名员工的家，然后是第 1 名、第 4 名和第 3 名。
在第二个样例中，当使用两辆出租车时，可以达到最小费用 3700：其中一辆车先去第 1 名员工的家，再去第 2 名员工的家；另一辆车先去第 3 名员工的家，再去第 4 名员工的家。