Minimum Additional Trucks

Given a network of n warehouses, m routes connecting these warehouses, and t trucks, each truck having a maximum travel distance and a limit on the number of warehouses it can visit, determine the minimum number of additional trucks required such that the trucks can cover all the routes.

The total distance that needs to be covered is defined as the sum of all the distances of the given routes. Each truck contributes by its maximum travel distance. If the sum of the maximum distances of the available trucks is less than the total route distance, additional trucks are needed.

The number of additional trucks required is calculated using the formula

$$\text{additional trucks} = \left\lceil \frac{\text{total route distance} - \text{sum of truck distances}}{\max(\text{truck distances})} \right\rceil$$

Note that although a truck's visiting capacity is provided, it is not used in the computation.

Input: The input is read from stdin and consists of the number of warehouses, routes, and trucks followed by details about each route and each truck.

Output: Output the minimum number of additional trucks required to cover the total route distance.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

n m t
u1 v1 d1
u2 v2 d2
... (m lines)
max_distance1 capacity1
max_distance2 capacity2
... (t lines)

Where:

• n is the number of warehouses.
• m is the number of routes.
• t is the number of trucks.
• Each route is specified by two warehouse indices u, v and a distance d.
• Each truck is specified by its maximum travel distance and its capacity (number of warehouses it can visit).

outputFormat

The output is a single integer printed to standard output (stdout) representing the minimum number of additional trucks required.

## sample

4 5 2
1 2 10
2 3 15
3 4 5
4 1 20
2 4 25
20 3
30 4

1