유물 도둑

마녀에게서 겨우 도망친 현욱은 여행을 계속했다. 여행 도중 현욱은 어떤 유적에 도착했다. 이 유적은 N개의 구역으로 이루어져 있고, 구역을 잇는 M개의 길이 있다. 길은 양방향이라 어느 쪽으로든 지날 수 있으며, 길을 지나는 데 1분이 걸린다. 모든 구역은 서로 연결되어 있어 어느 구역에서든 다른 구역으로 갈 수 있다.

유적에서는 발굴이 진행 중이고, 지금부터 K분 뒤에 발굴이 끝날 예정이다. 발굴단은 구역마다 어떤 가치의 유물이 나올지 미리 계산해 두었고, 현욱은 이 정보를 몰래 입수해 가장 가치가 높은 유물이 있는 구역으로 가서 유물을 훔치려 한다.

발굴단도 유물 도둑을 경계하므로 훔치지 못하도록 구역을 감시한다. 현욱은 최대한 안전하게 유물을 가져가려고 하므로 감시하는 구역에는 가지 않는다. 현욱은 감시 일정표를 미리 입수했는데, 일정표에는 Q개의 일정이 적혀 있고 각 일정은 Ti와 Xi로 이루어진다. 이 값은 Ti분부터 1분 동안 Xi 구역을 감시한다는 뜻이다. Ti분에 누군가 Xi 구역을 감시하고 있다면 현욱은 그 구역에 방문할 수 없고, Ti + 1분이 되면 다시 방문할 수 있다.

또 현욱은 한 구역에 계속 머물면 발굴단이 눈치챌 수 있으므로 한 구역에 머무르지 않고, 한 장소에 도착하는 즉시 다른 장소로 이동한다.

현욱은 지금 1번 구역에 있고, 정확히 K분이 지나 발굴이 끝나자마자 가장 가치가 높은 유물이 있는 구역에서 유물을 챙겨 도망가려 한다. 현욱이 감시를 피해 정확히 K분 뒤에 방문할 수 있는 구역 중 유물의 가치가 가장 높은 구역의 가치와 그런 구역의 개수를 구하는 프로그램을 작성하자.

첫째 줄에 N, M, Q, K가 주어진다.

다음 줄에 각 구역의 유물 가치를 나타내는 정수 N개가 주어진다. 각 유물의 가치는 1 이상 109 이하의 정수이다.

이어서 M개의 줄에 Xi, Yi (1 ≤ Xi, Yi ≤ N)가 공백으로 구분되어 주어진다. 이는 구역 Xi와 Yi를 연결하는 길이 있다는 뜻이다.

이어서 Q개의 줄에 일정표의 정보 Ti, Xi (1 ≤ Ti ≤ K, Ti는 정수, 1 ≤ Xi ≤ N)가 공백으로 구분되어 주어진다. 이는 시간 Ti부터 Xi 구역을 1분 동안 감시한다는 뜻이다.

첫째 줄에 정확히 K분 뒤에 도착할 수 있는 구역 중 유물의 가치가 가장 높은 구역의 가치와 그런 구역의 개수를 공백으로 구분하여 출력한다. 만약 정확히 K분 뒤에 도착할 수 있는 구역이 없으면 -1을 출력한다.

• 1 ≤ N ≤ 104
• 1 ≤ M ≤ 105
• 0 ≤ Q ≤ 300
• 1 ≤ K ≤ 109