407759: GYM102890 J Jaime's greedy delivery

It is year 2040 and teleportation is now a real thing, at least, between certain pairs of cities. This has been a huge improvement for Jaime's package delivery company, since now it is possible to travel between certain cities in a fixed amount of time $$$K$$$, instead of the usual variable time between cities because of the heavy traffic or the long distances. There are a total of $$$N$$$ cities in Jaime's world, and $$$M$$$ pairs of cities where Jaime can use teleportation to move between them. If teleportation can be used between the cities $$$a$$$ and $$$b$$$, then teleportation can be used also to move between cities $$$b$$$ and $$$a$$$.

This new technology also encouraged Jaime's greed. Instead of having employees to carry packages, he fired all of them and he is the only one working for the company. For Jaime, the less employees the company has, the more profit, hence, the maximum profit achievable is when there is only one employee, himself.

Jaime was hired by a well known e-commerce site to deliver a delivery order of packages for them. A delivery order consists of $$$O$$$ packages, each package has to be delivered to city $$$o_i$$$, and they should be delivered in the order given by the e-commerce site. This is, if the delivery order is $$$O=[1, 2, 5]$$$, then Jaime should deliver the first package to city $$$1$$$, the second package to city $$$2$$$ and the third package to city $$$5$$$, and he should deliver them in this specific order. Jaime will pick the $$$O$$$ packages to deliver and the order in which these should be delivered always in city $$$1$$$. Since the e-commerce site claims they always deliver the packages faster than all their competitors they need Jaime to deliver all the packages and return to the warehouse in a time no greater than $$$T$$$.

Jaime is well known in all the cities as he has been working delivering packages in all them for more than 20 years, and on every delivered package there is always someone waiting for Jaime to request an special delivery, the special delivery is simple, they just need a package to be delivered to the city $$$d_i$$$ and they will pay Jaime $$$v_i$$$ if Jaime takes the job. As Jaime's greed makes him want always more money, he may decide to take the special delivery getting him out of his original schedule. If Jaime decides to take a special delivery he will deliver that package immediately and then he will continue with his original delivery order (for which he was hired by the e-commerce site) from the city where the special package was delivered.

Given the order list given by the E-Commerce site to Jaime, and the list of special requests he will get on each delivered package, help him finding the maximum amount of extra money he can get complying with the e-commerce site time restrictions.

The first line contains three integer numbers separated by a space $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \leq N \leq 1000$$$, $$$1 \leq M \leq 10000$$$, $$$1 \leq K \leq 10$$$). representing, respectively the number of cities, the number of pairs of cities that can be used for teleportation, and the fixed amount of time it takes to teleport between cities. The next $$$M$$$ lines contain two integer numbers separated by a space $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq N$$$), representing that Jaime can be teleported between cities $$$a_i$$$ and $$$b_i$$$. The next line contains two integer numbers $$$O$$$ and $$$T$$$ ($$$1 \leq O \leq 1000$$$, $$$1 \leq T \leq 10^4$$$), representing the number of packages Jaime has to deliver and the maximum time he has to deliver all packages and return to the warehouse. The next line contains $$$O$$$ integer numbers separated by a space, where the $$$i$$$-th number in the line represents $$$o_i$$$ ($$$1 \leq o_i \leq N$$$), the city where the $$$i$$$-th package should be delivered. Each of the following $$$O$$$ lines in the input contains two integer numbers separated by a space, representing the city $$$d_i$$$ ($$$1 \leq d_i \leq N$$$) where the package of the special request in the $$$i$$$-th delivered package should be delivered and the value $$$v_i$$$ ($$$1 \leq v_i \leq 100$$$) Jaime will get if he accepts the special delivery.

Output a line with a single integer number, the maximum amount of extra money Jaime can get from the special deliveries complying with the e-commerce site restrictions. In case Jaime can not comply with the time restrictions given, print a single line with the string Impossible

5 4 1
1 2
2 3
3 4
4 5
2 8
5 2
2 10
5 20

10