题目描述

小明買了一台電動車，其電池容量為 $B$ 。小明知道電動車的初始電量 $b$ ，他要規劃從起點開到終點的路線，使得所需的充電費用越少越好。電動車在一些路段會耗電（如平路或是上坡），在一些路段會充電（如下坡）。這些充電路段是不會收費的。我們用一個有向圖表示地圖，邊的權重代表電動車開過此邊會讓電量增加或減少，如果開過此邊會充電，則邊的權重為一個正數，反之如果開過此邊會耗電，則邊的權重為一個負數。我們假設圖沒有正環。

電動車在行駛時，電量需要永遠大於等於 $0$ ，而且無論充電量多大，電量最多為 $B$ 。更明確地說，令 $p$ 為電動車目前電量，並考慮一個權重為 $w$ 的邊：如果 $w$ 非負數，則電動車一定可以開過此邊（即使電量 $p=0$ ），且剩餘電量為 $\min(B, p+w)$ ；如果 $w$ 是負數，且 $p+w \ge 0$ ，則電動車可以開過此邊，且開過此邊後的剩餘電量為 $p+w$ ；然而，如果 $p+w<0$ ，則電動車無法開過此邊。

地圖上有一些節點是充電站，小明可以經過多個充電站，因為充電要花時間找充電樁，小明決定路途中最多只用一個充電站充電。充電一單位的價格是一塊錢，小明的目標是花最少的錢到達目的地。

舉例來說，考慮以下三個圖，我們用方形節點代表充電站，圓形節點則無法充電。假設電池容量 $B=100$ ，起點為 $s$ ，終點為 $t$ ，且初始電量為 $20$ 。

在下圖中，電動車可以從 $s$ 抵達 $t$ ，且最小充電費用為 $0$ 。

:::align{center} :::

在下圖中，電動車無法從 $s$ 抵達 $t$。

:::align{center} :::

在下圖中，電動車可以從 $s$ 抵達 $t$，且最小充電費用為 $35$。

:::align{center} :::

输入格式

$$\begin{aligned} &n \; m \; s \; t \\ &B \; b \\ &u_1 \; v_1 \; w_1 \\ &u_2 \; v_2 \; w_2 \\ &\vdots \\ &u_m \; v_m \; w_m \\ &g \; p_1 \; p_2 \; \cdots \; p_g \end{aligned}$$

• $n$ 為節點數。
• $m$ 為邊數。
• $s$ 為起點編號。
• $t$ 為終點編號。
• $B$ 為電池容量。
• $b$ 為電池初始電量。
• $u_i, v_i, w_i$ 代表圖中有一個邊由節點 $u_i$ 至節點 $v_i$，且權重為 $w_i$。
• $g$ 為充電站個數。
• $p_i$ 為第 $i$ 個充電站的節點編號。

输出格式

$$a$$

• $a$ 代表最少所需的充電費用。如果不存在路徑抵達終點，則 $a = -1$。

6 5 1 6
100 20
1 2 -5
2 3 10
3 4 -25
4 5 5
5 6 -5
1 4

0

7 7 1 7
100 20
1 2 -15
2 3 200
3 4 -60
3 5 -80
4 6 -70
5 6 -40
6 7 20
1 6

-1

7 7 1 7
100 20
1 2 -10
2 3 -5
3 4 -20
3 5 -30
4 6 -40
5 6 -10
6 7 20
1 3

35

7 7 1 7
100 60
1 2 -10
2 3 -5
3 4 -20
3 5 -30
4 6 -40
5 6 -10
6 7 -5
0

0

提示

測資限制

• $1 \le n\le 10^3$。
• $1 \le m\le 10^4$。
• $1 \le s,t\le n$。
• $1 \le B\le 10^9$。
• $0 \le b\le B$。
• $1 \le u_i, v_i\le n$，且 $u_i \neq v_i$。
• $-10^9 \le w_i\le 10^9$。
• $0 \le g\le n$。
• $1 \le p_i \le n$。
• 保證圖沒有正環。
• 輸入的數皆為整數。

評分說明

本題共有四組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

子任務	分數	額外輸入限制
1	15	輸入滿足所有路段都不會充電，即 $w_i\le 0$， 且沒有充電站，即 $g = 0$。
2	30	輸入滿足所有路段都不會充電，即 $w_i\le 0$。
3	23	輸入滿足沒有充電站，即 $g = 0$。
4	32	無額外限制。