題目描述

I國和S國正在戰鬥，由於前綫戰局僵持不下，所以指揮官決定派出一支軍隊從大本營（1號地點）繞後偷襲敵方基地（N號地點）。由於新一輪的後勤補給還沒到，所以戰士們沒能給裝甲車加滿油，所以他們有可能到不了目標地點就沒油了。但是他們途中會經過一些我方據點（2~N-1號地點），其中一些據點有油料儲備，戰士們可以在那裏加油。現在給你行軍路綫的地圖，請你給他們選擇一條合適的路綫，使得他們可以抵達敵方基地，而且指揮官想讓部隊能有一定的戰鬥力，所以他希望到達基地時可以剩下盡量多的油料。

輸入格式

第一行有四個整數：地點總數 N, 有油料儲備的據點個數 M, 道路數量 P, 一開始部隊的油量 Q

第二行有M個整數：有油料的據點編號Oi

第三行有M個整數：有油料的據點的據點的油料儲備量Pi

接下來P行每行有三個數：道路起點 Ai, 道路終點 Bi, 走這條道路的耗油量 Qi

輸出格式

輸出一行：如果油料足夠讓部隊抵達地方基地，則輸出剩餘油料量，否則輸出"Mission Impossible!"。

Samples

["4 1 7 14\r\n3 \r\n3 \r\n1 3 7\r\n2 1 10\r\n2 3 10\r\n2 4 1\r\n3 1 4\r\n3 2 3\r\n4 1 5\r\n","5 2 8 3\r\n2 3 \r\n10 6 \r\n1 3 18\r\n2 4 11\r\n3 1 8\r\n3 2 12\r\n3 5 5\r\n4 1 9\r\n4 2 16\r\n5 4 5\r\n"]

["6","Mission Impossible!"]

提示

第一個範例：

1.先從起點（1號地點）消耗7的油料抵達3號地點，還剩14-7=7的油料

2.在3號地點補充3的油料，還剩7+3=10的油料

3.從3號地點消耗3的油料移動到2號地點，還剩10-3=7的油料

4.從2號地點消耗1的油料移動到終點（4號地點），還剩7-1=6的油料

數據範圍：1<M<N<5000,1<P<15000,1<Q<150,1<=Oi<=N,1<=Pi<=50,1<=Ai,Bi<=N,1<=Qi<=50

原始資料

• Zero1 題號：a851
• Hydro 題號：Z0851
• Locale：zh_CN
• Display：practice