H. HDL Shipping Service
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

HDL is a multinational corporation which is renowned in logistics shipping service. You, a computer science student, would love to enroll their technology graduate trainee program. After 5 rounds of interview, you have made it to the final one, which is a technical round with the senior manager. He gave you an intricate problem that the company is encountering at the time:

In the HDL logistics network, there are $$$N$$$ shipping stations and $$$M$$$ 1-way shipping routes, meaning that station $$$U_i$$$ can send goods to $$$V_i$$$ with $$$D_i$$$ days. Among the $$$N$$$ shipping stations, there are $$$P$$$ gift's locations, $$$Q$$$ receive locations and 1 headquarter. Each of the $$$P$$$ gift's locations has $$$A_i$$$ gifts in the inventory and they can send the gifts to other stations through the network. Each of the $$$Q$$$ receive locations need to receive $$$B_i$$$ gifts. For the headquarter, it has unlimited number of gifts in the inventory but all gifts sent from headquarter spend double days to pass through a shipping route (all $$$D_i$$$ are doubled). Please note that one station can be headquarter, gift's location and receive location at the same time. Also you can send unlimited gifts through a shipping route at the same time. Find the earliest day that all $$$Q$$$ receive locations receive at least $$$B_i$$$ gifts, or tell it is impossible.

Struggling right after you heard the problem, the senior manager smirked, "Don't worry, many interviewees failed this task, you are just one of them…". To stand on your dignity, please solve the problem (and get the job).

Input

The first line consists of 4 integers, $$$N$$$, $$$M$$$, $$$P$$$ and $$$Q$$$, which corresponds to the number of shipping stations, 1-way shipping routes, gift's locations and receive locations the network has.

Input is then followed by $$$M$$$ lines, each having 3 integers, $$$U_i$$$, $$$V_i$$$ and $$$D_i$$$, denoting that a 1-way shipping route exists between $$$U_i$$$ and $$$V_i$$$, and gifts going through which would spend $$$D_i$$$ days, and $$$2 \times D_i$$$ days for all gifts sent from the headquarter.

For the following $$$P$$$ lines, each has 2 integers, $$$X_i$$$ and $$$A_i$$$, meaning that there is a gift's location at station $$$X_i$$$ with the inventory of $$$A_i$$$ gifts. Similarly, for the next $$$Q$$$ lines, each has 2 integers, $$$Y_i$$$ and $$$B_i$$$, indicating that there is a receive location at station $$$Y_i$$$ that needs to receive $$$B_i$$$ gifts.

The last line of the input consists of 1 integer $$$Z$$$, meaning that the headquarter is located at station $$$Z$$$.

$$$1 \leq N \leq 10^5$$$, $$$0\leq M\leq 2 \times 10^5$$$, $$$1\leq P, Q \leq 50$$$

$$$1 \leq U_i, V_i, X_i, Y_i, Z \leq N$$$

$$$1 \leq A_i, B_i\leq 10^5$$$, $$$1 \leq D_i\leq 10^9$$$

All $$$X_i$$$ are distinct. All $$$Y_i$$$ are distinct.

Output

Output a single integer: the earliest day that all $$$Q$$$ receive locations receive at least $$$B_i$$$ gifts. If it is impossible, output $$$-1$$$ instead.

Examples
Input
3 3 1 3
1 2 4
2 3 7
1 3 11
2 1
1 3
2 1
3 1
1
Output
8
Input
2 1 1 1
1 2 11
2 100
1 1
2
Output
-1
Note

In the first sample, the optimal solution will be:

  • The gift's location at station 2 shall send 1 gift to the receive location at station 3. It will take 7 days.
  • The headquarter shall send gifts to all other receive locations. It will take $$$2 \times 4 = 8$$$ days to reach station 2.