Building a Bridge to Wowdo

Geondeok, now the school's public relations ambassador, must introduce every lecture building of Konkuk University to the new students.

His job is to walk once around Ilgam Lake, which lies at the center of Konkuk University, and introduce every lecture building along the way, but some stretches are under construction, so he cannot pass through them. In a hurry, Geondeok decides to throw stones into the lake to build a stepping-stone path.

The lecture buildings are arranged in a circle around Ilgam Lake, and the buildings on either side of a building are neighbors. Since the arrangement is a circle, if there are N lecture buildings, building N and building 1 are also neighbors.

Inside Ilgam Lake there is an island called Wowdo. Geondeok will build stepping stones from the lecture buildings to Wowdo so that every building can reach every other building. However, Geondeok can only see K stones. Can Geondeok complete the stepping-stone path using the stones he has?

The first line gives the number of lecture buildings N, the number of construction stretches M, and the number of stones Geondeok has K, separated by spaces. The lecture buildings are numbered 1 through N.

The next line gives S1, S2, ..., SN, the numbers of stones that must be placed from each lecture building to Wowdo, separated by spaces. This means that ST stones must be placed from the T-th lecture building to Wowdo. Then M lines follow, each giving i and j. This means the path from the i-th lecture building to the j-th lecture building is under construction. The buildings i and j given here are neighbors. Each construction stretch is given only once.

Print YES if Geondeok can connect all the lecture buildings using the stones he has, and NO otherwise.

• 3 ≤ N ≤ 1,000,000
• 0 ≤ M ≤ N
• 1 ≤ i, j ≤ N
• 1 ≤ ST ≤ 1,000,000 for every integer T with 1 ≤ T ≤ N
• 0 ≤ K ≤ 5,000,000,000