17490번 - 일감호에 다리 놓기

학교의 홍보대사를 맡게 된 건덕이는 건국대학교의 모든 강의동을 신입생들에게 소개해야 한다.

건국대학교 중앙에 위치한 일감호를 따라 한 바퀴를 돌며 모든 강의동을 소개하는 것이 그의 일이지만, 몇몇 구간들이 공사 중이어서 그 구간을 통해서는 갈 수 없는 상황이다. 급한대로 건덕이는 호수에 돌을 던져 징검다리를 놓아 길을 만들어보려고 한다.

강의동은 일감호의 둘레에 따라 원형으로 배치돼 있으며, 강의동 양 옆의 강의동은 서로 이웃한다. 또, 원형으로 배치돼 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃한다.

일감호 안에는 와우도라는 섬이 있다. 건덕이는 한 강의실에서 다른 모든 강의실로 이동할 수 있도록 강의동에서 와우도까지 징검다리를 놓기로 했다. 하지만 건덕이의 눈에는 K개의 돌밖에 보이지 않는다. 건덕이는 주어진 돌을 활용해서 징검다리를 완성할 수 있을까?

첫째 줄에 강의동의 수 N, 공사구간의 수 M, 건덕이가 가진 돌의 수 K가 공백으로 구분돼 주어진다. 강의동은 1동부터 N동까지 존재한다.

다음 줄에는 강의동에서 와우도까지 놓아야하는 돌의 개수 S₁, S₂, ..., S_N이 공백으로 구분돼 주어진다. 이는 T번째 강의동에서 와우도까지 S_T개의 돌을 놓아야 함을 의미한다. 이어서 M개의 줄에 i, j가 주어진다. 이는 i번째 강의동에서 j번째 강의동까지 가는 길이 공사중임을 의미한다. 이 때 입력되는 i, j번째 건물은 이웃한 강의동이다. 공사중인 구역은 한 번만 주어진다.

건덕이가 가지고 있는 돌을 놓아 모든 강의동을 연결할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

• 3 ≤ N ≤ 1,000,000
• 0 ≤ M ≤ N
• 1 ≤ i, j ≤ N 
• 1 ≤ T ≤ N인 모든 정수 T에 대해 1 ≤ S_T ≤ 1,000,000
• 0 ≤ K ≤ 5,000,000,000