408050: GYM102966 N Newest Jaime's Delivery

Jaime's package delivery company is working on a new system to reduce the spending on vehicle fuel. Basically what they will do is to reduce the amount of fuel they load on a vehicle before it starts with its delivery order. Each morning Jaime takes a vehicle from warehouse $$$1$$$ which can hold a maximum of $$$F$$$ fuel to deliver $$$K$$$ packages, each of these packages should be delivered on one of the $$$N$$$ warehouse of Jaime's company, no two packages will be delivered in the same warehouse, and some warehouses may not receive a package in a day, also, Jaime can deliver the packages in any order he decides. Some warehouses have a fuel pump that can be used to load a maximum of $$$f_i$$$ fuel into the vehicle, Jaime can go to a warehouse even if he does not have to deliver a package to it just to load fuel, and everytime he goes to the a warehouse with a pump, he can load fuel even if he already loaded fuel in that warehouse.

As part of their vehicle fuel reduction program, Jaime has measured the amount of fuel $$$c_{u,v}$$$ it takes to travel from one warehouse to another. As measuring all pairs of warehouses is difficult and costly, Jaime measured only $$$M$$$ pairs of them. Jaime will make sure to travel from one warehouse $$$u$$$ to another warehouse $$$v$$$ during his delivery task only if he knows beforehand the amount $$$c_{u,v}$$$ of fuel he needs, and if the vehicle has at least $$$c_{u,v}$$$.

Jaime needs your help to determine what is the minimum amount of fuel he has to load on the vehicle before he starts his delivery task in order to deliver the $$$K$$$ packages and return to warehouse $$$1$$$?

The first line of input contains four integer numbers separated by a space, $$$N$$$, $$$M$$$, $$$K$$$, $$$F$$$ ($$$1 \leq N \leq 100$$$, $$$1 \leq M \leq \frac{(N)(N-1)}{2}$$$, $$$1 \leq K \leq 10$$$, $$$1 \leq F \leq 100$$$), representing the number of warehouses in Jaime's company, the number of pairs Jaime has measured the fuel needed to travel, the number of packages to deliver, and the maximum amount of fuel the vehicle can hold. The second line contains $$$K$$$ integer numbers separated by a space, each number represents a warehouse $$$w_i$$$ ($$$1 \leq w_i \leq N$$$) where Jaime has to deliver a package, all the numbers in this line are different. The next $$$M$$$ lines contains three integer numbers separated by a space, $$$u_i$$$, $$$v_i$$$, $$$c_{u_i,v_i}$$$, representing Jaime has measured going from $$$u_i$$$ to $$$v_i$$$ or from $$$v_i$$$ to $$$u_i$$$ needs $$$c_{u_i,v_i}$$$ fuel. The next line contains an integer number $$$P$$$ ($$$0 \leq P \leq N$$$), representing there are $$$P$$$ warehouses with pumps to load fuel. The next $$$P$$$ lines contains two integer numbers separated by a space $$$p_i$$$ and $$$f_i$$$, representing, at warehouse $$$p_i$$$, there is a pump where Jaime can load up to $$$f_i$$$ fuel.

Output a line containing a single integer number: the minimum amount of fuel Jaime has to load on the vehicle to deliver all packages and return to warehouse $$$1$$$. If this is not possible, print -1.

7 7 1 2
7
1 2 1
2 3 1
3 4 1
4 5 1
2 6 1
6 7 1
5 7 1
2
3 2
5 2

2

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

-1

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

2