In Case of an Invasion, Please. . .

Time limit3.5sMemory limit512 MB

Summary

Place people from n city nodes, with at most 10 capacity-limited shelters on a weighted road network, to minimize the latest arrival time at any shelter.

Level: Hard9 of 10
Topics: Binary search, BFS, Graph, Greedy
Solved: No attempts yet

Problem

After Curiosity discovered not just water on Mars, but also an aggressive, bloodthirsty bunch of aliens, the Louvain-la-Neuve municipal government decided to take precautionary measures; they built shelters in order to shelter everyone in the city in the event of an extraterrestrial attack.

Several alien-proof shelters have been erected throughout the city, where citizens can weather an alien invasion. However, due to municipal regulations and local building codes the shelters are limited in size. This makes it necessary for the government to assign every citizen a shelter to calmly direct themselves towards in the rare event of a fleet of UFOs blotting out the sun. On the condition that no shelter is assigned more people than it can fit, it is of the utmost importance that the time it takes until everyone has arrived at a shelter is minimized.

We model Louvain-la-Neuve as a network of n locations at which people live, connected by m bidirectional roads. Located at s points throughout the city are the shelters, each with a given maximum capacity. What is the minimum amount of time it takes for everyone to arrive at a shelter, when we assign people to shelters optimally?

The Louvain-la-Neuve municipal government has made sure that there is enough shelter capacity for its citizens and that all shelters can be reached from any location, i.e. it is always possible to shelter everyone in some way.

Input

On the first line are three integers, the number of locations $1 \le n \le 10^5$ , roads $0 \le m \le 2 \cdot 10^5$ , and shelters $1 \le s \le 10$ .
Then follows a line with n integers $0 \le p_i \le 10^9$ , indicating the number of people living at location $1 \le i \le n$ .
Then follow m lines containing three integers $1 \le u, v \le n$ and $1 \le w \le 10^9$ indicating that there is a bidirectional road connecting u and v that takes w time to traverse. For any two locations there is at most one road connecting them directly, and no road connects a location to itself.
Finally follow s lines with two integers $1 \le s_i \le n$ and $1 \le c_i \le 10^9$ , indicating that there is a shelter with capacity $c_i$ at location $s_i$ .

Output

Print the minimum amount of time it takes to shelter everyone.

Examples4

Example 1
Input
```
2 1 1
3 2
1 2 4
1 6
```
Expected output
```
4
```

Example 2

Input

Expected output

Example 3

Input

7 8 3
0 1 1 1 1 0 2
1 2 1
2 3 1
3 1 1
4 6 5
4 3 1
6 7 10
7 5 3
5 6 3
6 5
1 1
2 1

Expected output

Example 4
Input
```
2 1 1
0 2
1 2 1000000000
2 2
```
Expected output
```
0
```