题目内容

小红约了 $q$ 名同伴，打算在城里某一家馆子碰头。

路网里既有只准单向走的路段（行人车辆都受此限），也有可以来回走的路段。小红驾车按每公里 $2$ 分钟行进，同伴步行按每公里 $10$ 分钟行进。

已知小红出发路口、馆子所在路口，以及每名同伴所在路口。小红可以：

1. 径直把车开到馆子
2. 先绕去接上若干同伴，再一同抵达
3. 没接到的同伴则自己走过去

每名同伴只能二选一：坐小红的车，或全程步行，中途不许改主意。

请算出一种安排，让所有人抵达馆子的时刻尽可能早（以最晚到达的那人为准）。

输入描述

首行给出四个整数 $p, e, a, b$

• $p$: 全城路口一共有多少个（$1 \le p \le 10^{3}$）
• $e$: 路段一共有多少条（$1 \le e \le 10^{3}$）
• $a$: 小红开车起步的路口（$1 \le a \le p$）
• $b$: 馆子对应的路口（$1 \le b \le p$）

随后 $e$ 行，每行四个整数 $x, y, c, z$：路口 $x$、$y$ 之间铺着一条 $c$（$1 \le c \le 10^{2}$）公里长的路；$z=0$ 表示只能从 $x$ 开向 $y$，$z=1$ 表示两端都能走。

再下一行一个整数 $q$（$0 \le q \le 15$），即同伴人数。

再下一行 $q$ 个整数，即各同伴所在路口。

输出描述

输出一个整数：所有人抵达馆子的最短时间（分钟）。

样例1

输入

4 4 1 4
1 2 3 1
2 4 4 1
1 3 5 1
3 4 2 1
2
2 3

输出

20

说明

四个路口、四条双向路。小红在 $1$，馆子在 $4$，两名同伴在 $2$、$3$。

• 只接路口 $2$：车程 $1 \to 2 \to 4$，共 $7$ 公里、$14$ 分钟；路口 $3$ 的同伴步行 $3 \to 4$，共 $2$ 公里、$20$ 分钟。汇合时刻 $20$
• 两人都接上：车程更长，汇合时刻大于 $20$
• 因此最短为 $20$

样例2

输入

3 3 1 3
1 2 10 1
2 3 10 1
1 3 2 1
1
2

输出

40

说明

小红在 $1$，馆子在 $3$，一名同伴在 $2$。

• 直接去馆子再让同伴步行：$2 \to 3$ 为 $10$ 公里、$100$ 分钟
• 绕去路口 $2$ 再开到 $3$：车程 $20$ 公里、$40$ 分钟
• 因此最短为 $40$

提示

1. 车子能装多少人不设上限
2. 同一条路、同一个点都可以走多次
3. 数据保证每个人都能抵达馆子