TopCoder

Thumb nobody calls me tubby
HahA
甲土豆

User's AC Ratio

89.5% (34/38)

Submission's AC Ratio

51.8% (57/110)

Description

你,淉垞,是個剛上高中的小高一。
你很幸運的考上了天龍國最好的高中,王立天龍第一男子中學。
這間學校之所以被稱為最好的高中,除了因為有最好的設備、優良的師資、距離天龍第一女子中學只有一條街的距離等等因素外,還有一個很主要的原因,也就是「友情」。
沒錯,只要進入這間學校,所有人都可以獲得堅定不移、海枯石爛、白頭偕老的友情,也許高一還比較害羞,但是到了高三,就可以發現大家和樂融融的生活在一起了。
而你,淉垞,是個剛上高中的小高一,你很想馬上體會一下這種溫馨的感覺,於是你想要在學校逛逛,多多認識同學和學長。

王立天龍第一男子中學有很多的教室,每間教室透過一些魔動力傳送門連接,想要到別間教室必須通過這些魔動力傳送門,通過每個魔動力傳送門的時間是相等的。
因為下課時間有限,你又不想因為迷路或跑太遠來不及回來跟你的同班同學培養感情,你決定定下一個數量D,並且希望之後在探索某間教室的時候,如果聽到鐘聲,你隨時可以通過不多於數量D個的魔動力傳送門回到你的教室,這樣你才來得及在聽到上課鈴的時候趕回來。
因為這個原因,你只能探索所有距離你的教室不超過D個魔動力傳送門的教室。
你很想知道,如果把符合條件的教室都探索完,你最多可以認識多少同學和學長。

為了方便起見,你把自己的教室當作編號0。每間教室都有一個編號,教室裡會有一些學生,請問你最多可以邂逅多少同學和學長呢?

Input Format

第一行有兩個數字n,m,代表共有n間教室和m個魔動力傳送門。
第二行有n個不小於0且不大於104 的整數,分別代表每間教室有多少同學在裡面。
接下來有m行,
每行有兩個整數a,b,代表編號a的教室和編號b的教室之間有一座魔動力傳送門連接彼此。
最後一行有一個整數D。

對於30%的測試資料,滿足0≤n,m≤10。
對於100%的測試資料,滿足0≤n≤105 ,0≤m≤3*105 ,0≤a,b≤n-1。

Output Format

輸出你可以遇到的同學和學長的數量。

Sample Input

5 5
2 2 2 2 2
0 1
0 2
1 2
2 3
3 4
2

Sample Output

8

Hints

?

Problem Source

果茶
2015建中校內資訊能力競賽

Subtasks

For Testdata: 0 ~ 2, Score: 30
For Testdata: 3 ~ 6, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144