Problem Description

In the Kingdom of Paken, there are $ N $ towns connected by $ M $ one-way roads. The $ i $-th road connects town $ A_i $ to town $ B_i $. Additionally, $ P $ towns have an observatory each, and the observatory in town $ C_i $ is located at an altitude of $ D_i $.

ZRK is planning a drive trip. He will start from the observatory in town $ S $ and end his drive at the observatory in town $ T $ by moving through some roads. He can pass through the same town or road multiple times.

ZRK will always visit an observatory if he passes through a town that has one. His happiness starts at $ 0 $, but whenever he visits an observatory $ i $ (other than the starting one), his happiness increases by the absolute difference in altitudes between the current observatory $ i $ and the previously visited observatory $ j $, i.e., $ |D_i - D_j| $.

He wants his happiness to be at least $ K $ by the end of his drive. Determine the minimum length of the route that satisfies this condition.

The length of a route is defined as the total number of times all roads are traversed. For example, if he follows the route $3 \rightarrow 5 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5 \rightarrow 4$, the route length is $ 6 $.

If no route can make his happiness at least $ K $, output $ -1 $ instead.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ P $ $ S $ $ T $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ ... $ A_M $ $ B_M $ $ C_1 $ $ D_1 $ $ C_2 $ $ D_2 $ ... $ C_P $ $ D_P $

Output Format

Output the minimum length of the route that satisfies the condition. If no such route exists, output $ -1 $ instead.

Sample Input and Output

Sample Input #1

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

Sample Output #1

6

Sample Input #2

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

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

7

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq N \leq 50$
• $1 \leq M \leq N(N-1)$
• $1 \leq P \leq N$
• $1 \leq S, T \leq N$
• $1 \leq K \leq 10^9$
• $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq M)$
• $A_i \neq B_i$ $(1 \leq i \leq M)$
• $(A_i, B_i) \neq (A_j, B_j)$ $(i \neq j)$
• $1 \leq C_i \leq N$ $(1 \leq i \leq P)$
• $1 \leq D_i \leq 10^5$ $(1 \leq i \leq P)$
• $C_i \neq C_j$ $(i \neq j)$
• There exists an $ i $ such that $ C_i = S $ and a $ j $ such that $ C_j = T $.

Subtasks

This task has two subtasks:

1. (300 points) $K \leq 20$
2. (700 points) No additional constraints.

见题面 Input 部分

见题面 Output 部分