할로윈의 양아치

Trick or Treat!!

10월 31일 할로윈 밤에는 거리 곳곳에서 아이들이 친구와 모여 사탕을 받으러 돌아다닌다. 올해 할로윈에도 많은 아이가 즐겁게 보냈지만, 일찍 잠에 빠진 스브러스만은 할로윈 밤을 즐길 수 없었다. 뒤늦게 일어나 사탕을 얻으려 혼자 돌아다녀 보지만 사탕은 이미 바닥나 하나도 얻지 못했다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 일은 어렵지 않다. 스브러스는 매우 공평한 사람이라 한 아이의 사탕을 빼앗으면 그 아이 친구들의 사탕도 모조리 빼앗아버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고, $K$명 이상의 아이가 울기 시작하면 울음소리가 공명해 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 빼앗을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 모든 아이는 스브러스를 피해 갈 수 없다.

첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, $1 \leq K \leq \min\left\{N, 3\ 000\right\}$)

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 $c_1, c_2, \cdots, c_N$이 주어진다. ($1 \leq c_i \leq 10\ 000$)

셋째 줄부터 $M$개 줄에 걸쳐 각각의 줄에 정수 $a$, $b$가 주어진다. 이는 $a$와 $b$가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. ($1 \leq a, b \leq N$, $a \neq b$)

스브러스가 어른들에게 들키지 않고 아이들로부터 빼앗을 수 있는 최대 사탕의 수를 출력한다.