Minimum Transportation Cost

A logistics company needs to transport a batch of goods from port A to port B over exactly n days. In the process, the goods normally have to transit through several intermediate ports. The company usually has a fixed route to closely monitor and manage the transport. However, due to various factors, on some days a certain port might be unable to load or unload goods. In such cases the route must be modified so that the goods still arrive at the destination on time.

The goal is to design an n-day transportation plan that minimizes the total cost.

Formally, you are given an integer n representing the number of days (i.e., the number of legs in the journey), and an integer m representing the total number of ports (numbered from 1 to m, where 1 represents port A and m represents port B). There are r directed routes. Each route is described by three integers u, v, and c indicating that you can travel from port u to port v in one day with cost c.

In addition, there are some restrictions: on certain days, some ports (except port A and port B) might be temporarily unavailable. You are given an integer k followed by k lines; each line contains two integers: day and port. This means that on the specified day the given port is unavailable to receive goods. Note that if a route would deliver goods to a port that is unavailable on that day, it cannot be used. Port B is always available regardless of the restrictions.

Your task is to determine the minimum total cost to transport the goods from port 1 to port m in exactly n days. If it is impossible to design such a plan under the given restrictions, output -1.

The DP recurrence can be formulated in \(\LaTeX\) as follows:

\(dp[i][v] = \min_{(u,v) \in E} \{ dp[i-1][u] + cost(u,v) \}\)

with the condition that if \(v \neq m\) and \(v\) is marked unavailable on day \(i\), then the transition is not allowed. The answer is \(dp[n][m]\).

inputFormat

The first line contains three integers: n (the number of days), m (the number of ports), and r (the number of routes).

The next r lines each contain three integers: u, v, and c, representing a directed route from port u to port v with cost c.

The next line contains an integer k representing the number of port unavailability records.

The following k lines each contain two integers: day and port, meaning that on that day, the specified port (if it is not port 1 or port m) is unavailable.

outputFormat

Output a single integer -- the minimum cost to transport the goods from port 1 to port m in exactly n days. If there is no valid transportation plan, output -1.

sample

1 2 1
1 2 10
0

10