In Case of an Invasion, Please. . .#9886
After Curiosity discovered not only water on Mars but also an aggressive, bloodthirsty bunch of aliens, the municipal government of Louvain-la-Neuve decided to take precautionary measures: it built shelters capable of housing 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 size of the shelters is limited. Therefore, the government must assign every citizen a shelter to head calmly towards in the rare event that a fleet of UFOs blots out the sun. No shelter may be assigned more people than it can hold, and subject to this constraint, it is of the utmost importance to minimize the time until everyone has reached a shelter.
We model Louvain-la-Neuve as a network of locations where people live, connected by bidirectional roads. The shelters are located at points throughout the city, and each of them has a given maximum capacity. What is the minimum time needed for everyone to reach a shelter if people are assigned to shelters optimally?
The municipal government of Louvain-la-Neuve has made sure that the total shelter capacity is sufficient for all citizens and that every shelter can be reached from any location, so it is always possible to shelter everyone.
The first line contains three integers: the number of locations n~(1 \le n \le 10^5), the number of roads m~(0 \le m \le 2 \cdot 10^5) and the number of shelters s~(1 \le s \le 10).
The second line contains integers p_1, p_2, \dots, p_n~(0 \le p_i \le 10^9), where p_i is the number of people living at location .
Each of the next lines contains three integers , and w~(1 \le u, v \le n, 1 \le w \le 10^9), meaning that there is a bidirectional road between locations and that takes units of time to traverse. Any two locations are connected directly by at most one road, and no road connects a location to itself.
Each of the last lines contains two integers s_i and c_i~(1 \le s_i \le n, 1 \le c_i \le 10^9), meaning that there is a shelter with capacity c_i at location s_i.
Print the minimum time needed to shelter everyone.
Example 1
Example 2
Example 3
Example 4