개미굴

개미들이 먹이를 찾아 버려진 개미굴을 뒤지고 있다. 개미굴에는 방이 $n$개 있고 방을 잇는 통로가 $n-1$개 있다. 어느 방에서 다른 어느 방으로 가는 경로는 항상 하나뿐이다. 즉 방과 통로는 트리를 이룬다.

통로가 하나만 이어진 방에는 개미굴 입구가 있다. 입구마다 개미 $m_1, m_2, \dots, m_g$마리로 이루어진 무리 $g$개가 기다리고 있다. 무리는 차례로 들어가고, 앞의 무리가 개미굴 안에서 모두 빠져나온 뒤에 다음 무리가 들어간다. 개미굴 안에서 개미는 이렇게 움직인다.

• 아직 지나지 않은 통로가 $d$개 있는 방에 무리가 들어오면, 무리는 크기가 같은 무리 $d$개로 나뉜다. 새로 생긴 무리는 각각 통로 $d$개 가운데 하나를 따라간다. $d=0$이면 무리는 개미굴을 빠져나간다.
• 똑같이 나눌 수 없으면 강한 개미가 약한 개미를 잡아먹어서 정확히 나누어떨어질 때까지 수를 줄인다. 개미 수는 0까지도 줄어들 수 있으므로 이런 분할은 언제나 가능하다. 나누어떨어지게 만드는 일을 막을 방법은 없다. 개미는 자기 자신도 잡아먹을 수 있고, 무리의 크기가 $d$보다 작으면 마지막 한 마리가 그렇게 한다.

아래 그림은 아직 지나지 않은 통로가 3개인 방에 개미 $m$마리가 들어와서 각각 $\lfloor m/3 \rfloor$마리인 무리 3개로 나뉘는 모습이다.

배고픈 개미핥기가 통로 하나를 파고들어서 그 통로를 지나는 개미를 모두 먹을 수 있게 되었다. 그런데 개미핥기도 개미만큼 수에 까다로워서, 지나가는 무리의 크기가 정확히 $k$일 때만 그 무리를 먹는다. 개미핥기가 먹는 개미가 모두 몇 마리인지 구하라.

첫째 줄에 정수 $n$, $g$, $k$가 공백 하나로 구분되어 주어진다 ($2 \le n, g \le 1{,}000{,}000$, $1 \le k \le 10^9$). 차례로 방의 수, 개미 무리의 수, 개미핥기가 한 번에 먹는 개미 수이다. 방 번호는 1번부터 $n$번까지이다.

둘째 줄에 정수 $m_1, m_2, \dots, m_g$가 공백 하나로 구분되어 주어진다 ($1 \le m_i \le 10^9$). $m_i$는 모든 입구에서 $i$번째로 들어가는 무리의 개미 수이다.

이어지는 $n-1$개 줄에는 개미굴의 통로가 하나씩 주어진다. $i$번째 줄에는 정수 $a_i$와 $b_i$가 공백 하나로 구분되어 주어지고 ($1 \le a_i, b_i \le n$), 방 $a_i$와 방 $b_i$가 통로로 이어져 있다는 뜻이다. 개미핥기는 입력에서 가장 먼저 주어진 통로를 파고들었다.

개미핥기가 먹는 개미 수를 한 줄에 출력한다.

첫 번째 예제에서 방 2번, 3번, 5번, 7번 옆에 개미 무리가 5개씩 있다. 개미핥기는 방 2번에서 출발한 첫 번째 무리에서 3마리를 먹고, 방 3번, 5번, 7번에서 출발한 네 번째 무리와 다섯 번째 무리에서 각각 3마리씩 먹는다. 그림의 X 표시가 개미핥기가 파고든 통로이다.