시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 256 MB80272138.889%

문제

태영이와 승한이는 연말을 맞아 해외 여행을 떠났다. 여행지에서 열심히 돌아다니던 둘은 점심 시간이 얼마 남지 않았다는 것을 깨달았다.

정확히 K시간 뒤부터 점심시간이고, 둘은 최대한 괜찮은 음식점에 찾아가서 식사를 하고 싶다. 하지만 문제는 태영이와 승한이의 음식 취향이 정반대라는 것이다.

태영이는 음식이 짤수록 좋아하고 승한이는 음식이 싱거울수록 좋아한다.

태영이와 승한이가 있는 마을에는 N개의 음식점이 있고, 이들은 M개의 길로 연결되어 있다. 모든 길은 지나다니는데 정확히 10분의 시간이 걸린다.

두 음식점을 연결하는 길이 여러 개 존재할 수도 있고, 한 음식점에서 출발해서 같은 음식점으로 돌아오는 길이 존재할 수도 있다. 

각 음식점은 정확히 하나의 음식만 판매하고, i번째 음식점에서 판매하는 음식의 '짠 정도'는 정수 Ci로 나타난다.

태영이와 승한이는 상대방에게 양보할 생각이 조금도 없고, 둘 사이의 힘의 균형이 팽팽하게 유지되기 때문에 남은 K시간동안 다음 규칙을 따라 이동하게 된다.

  1. 첫 20분 동안 태영이가 승한이를 질질 끌고 간다.
  2. 다음 10분 동안 승한이가 태영이를 질질 끌고 간다.
  3. 다음 10분 동안 태영이가 승한이를 질질 끌고 간다.
  4. 다음 20분 동안 승한이가 태영이를 질질 끌고 간다.
  5. 1~4번 과정이 총 K시간 동안 반복된다.

예를 들어 2시간 즉, 120분이 남은 경우에는 1~4번 과정을 2번 반복하면 (20+10+10+20)+(20+10+10+20)분으로 총 120분이 지나가게 된다.

이 때 자신이 다른 사람을 질질 끌고 가는 시간에 움직이지 않고 멈춰 있을 수도 있지만, 태영이와 승한이의 각 차례가 끝날 때는 항상 어떤 음식점에 위치해 있어야 한다. 

즉, 길 중간에 멈춰설 수는 없다.

태영이와 승한이는 마을 지도를 갖고 있고, 위 규칙대로 움직이되 자신에게 최대한 이득이 되는 방향으로 움직인다.

즉, 태영이는 최대한 짠 정도가 높은 음식을 먹을 수 있는 방향으로, 승한이는 최대한 짠 정도가 낮은 음식을 먹을 수 있는 방향으로 움직인다.

둘은 현재 1번 음식점에 있다. 이 때 태영이와 승한이가 먹게 될 음식의 '짠 정도'를 구하여라.

입력

첫 줄에 N, M, K가 사이에 공백을 두고 순서대로 주어진다. (1 ≤ N ≤ 2 × 105, 0 ≤ M ≤ 5 × 105, 0 ≤ K ≤ 5 × 105)

두 번째 줄에는 C1, C2, ... CN 이 사이에 공백을 두고 순서대로 주어진다. (0 ≤ Ci ≤ 109)

세 번째 줄부터 M+2번째 줄에서는 각 줄에 두 자연수 SiEi가 주어지는데, 이는 Si번 음식점과 Ei번 음식점이 도로로 연결되어 있음을 의미한다. (1 ≤ Si, Ei N)

출력

태영이와 승한이가 먹게 될 음식의 ‘짠 정도’를 첫 줄에 출력한다.

예제 입력 1

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

예제 출력 1

3