A logistics company needs to transport a batch of goods from port A to port B. Due to the large volume of goods, it will take $n$ days to complete the transport. During the transport process, the goods usually stop at several intermediate ports. The logistics company typically designs a fixed transport route to implement strict management and tracking of the entire process. Due to various factors, sometimes a certain port may be unable to load or unload goods. In such cases, the transport route must be modified to ensure the goods reach their destination on time. However, modifying the route is a very troublesome task and incurs additional costs. Therefore, the logistics company hopes to establish an $n$-day transport plan that minimizes the total cost.

Input

The first line contains four integers $n$ ($1 \le n \le 100$), $m$ ($1 \le m \le 20$), $K$, and $e$. $n$ represents the number of days required for transport, $m$ represents the total number of ports, $K$ represents the cost of each route modification, and $e$ represents the number of shipping routes. The next $e$ lines each contain three integers, representing the two port IDs connected by the route and the route length ($>0$). Port A is numbered 1, and port B is numbered $m$. The transport cost per unit length is 1. Routes are bidirectional.

The next line contains an integer $d$. The following $d$ lines each contain three integers $P$ ($1 < P < m$), $a$, and $b$ ($1 \le a \le b \le n$), indicating that port $P$ is unavailable for loading or unloading from day $a$ to day $b$ (inclusive). A single port may be unavailable during multiple time periods. However, at any given time, there is at least one transport route from port A to port B.

Output

Output a single integer representing the minimum total cost. The total cost is defined as the sum of the transport route lengths over $n$ days plus $K \times (\text{number of route changes})$.

Examples

Input 1

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

Output 1

32

Note

For the first three days, the route is 1-4-5, and for the last two days, the route is 1-3-5. The total cost is $(2+2) \times 3 + (3+2) \times 2 + 10 = 32$.