Relic Thief
Time limit2sMemory limit512 MB
A walker moves one edge per minute from zone 1 and never waits; find the highest relic value among zones occupied at exactly K minutes given a short surveillance list.
Problem
After barely escaping from the witch, Hyeonuk continued his journey. Along the way he arrived at some ruins. The ruins consist of N zones, joined by M paths. Each path is two-way, so it can be crossed in either direction, and crossing a path takes 1 minute. Every zone is connected, so any zone can be reached from any other.
Excavation at the ruins is underway and is expected to finish K minutes from now. The excavation team has already computed what value of relic each zone will yield, and Hyeonuk secretly obtained this information and plans to go to a zone with the most valuable relic and steal it.
The excavation team is wary of relic thieves, so they watch the zones to prevent theft. Hyeonuk wants to take the relic as safely as possible, so he avoids zones under surveillance. He has already obtained the surveillance schedule, which lists Q entries, and each entry consists of Ti and Xi. This means that zone Xi is watched for 1 minute starting at minute Ti. If someone is watching zone Xi at minute Ti, Hyeonuk cannot visit that zone, and at minute Ti + 1 he can visit it again.
Also, if he stays in one zone, the excavation team may notice him, so Hyeonuk does not remain in a zone; the moment he arrives at a place, he moves to another place.
Hyeonuk is now in zone 1, and exactly K minutes later, as soon as the excavation ends, he wants to take the relic at the zone with the highest value and run away. Write a program that helps Hyeonuk avoid surveillance and find, among the zones he can visit exactly K minutes later, the value of the most valuable relic and the number of such zones.
Input
The first line gives N, M, Q, and K.
The next line gives N integers representing the relic value of each zone. Each relic value is an integer between 1 and 109 inclusive.
The next M lines give Xi and Yi (1 ≤ Xi, Yi ≤ N), separated by spaces. This means there is a path connecting zones Xi and Yi.
The next Q lines give schedule entries Ti and Xi (1 ≤ Ti ≤ K, Ti is an integer, 1 ≤ Xi ≤ N), separated by spaces. This means that from time Ti, zone Xi is watched for 1 minute.
Output
On the first line, print the value of the most valuable relic among the zones reachable exactly K minutes later, and the number of such zones, separated by a space. If no zone is reachable exactly K minutes later, print -1.
Constraints
- 1 ≤ N ≤ 104
- 1 ≤ M ≤ 105
- 0 ≤ Q ≤ 300
- 1 ≤ K ≤ 109