你,淉垞,是個剛上高中的小高一。
你很幸運的考上了天龍國最好的高中,王立天龍第一男子中學。
這間學校之所以被稱為最好的高中,除了因為有最好的設備、優良的師資、距離天龍第一女子中學只有一條街的距離等等因素外,還有一個很主要的原因,也就是「友情」。
沒錯,只要進入這間學校,所有人都可以獲得堅定不移、海枯石爛、白頭偕老的友情,也許高一還比較害羞,但是到了高三,就可以發現大家和樂融融的生活在一起了。
而你,淉垞,是個剛上高中的小高一,你很想馬上體會一下這種溫馨的感覺,於是你想要在學校逛逛,多多認識同學和學長。
王立天龍第一男子中學有很多的教室,每間教室透過一些魔動力傳送門連接,想要到別間教室必須通過這些魔動力傳送門,通過每個魔動力傳送門的時間是相等的。
因為下課時間有限,你又不想因為迷路或跑太遠來不及回來跟你的同班同學培養感情,你決定定下一個數量D,並且希望之後在探索某間教室的時候,如果聽到鐘聲,你隨時可以通過不多於數量D個的魔動力傳送門回到你的教室,這樣你才來得及在聽到上課鈴的時候趕回來。
因為這個原因,你只能探索所有距離你的教室不超過D個魔動力傳送門的教室。
你很想知道,如果把符合條件的教室都探索完,你最多可以認識多少同學和學長。
為了方便起見,你把自己的教室當作編號0。每間教室都有一個編號,教室裡會有一些學生,請問你最多可以邂逅多少同學和學長呢?
第一行有兩個數字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。
輸出你可以遇到的同學和學長的數量。
?
果茶
2015建中校內資訊能力競賽
No. | Testdata Range | Score |
---|---|---|
1 | 0~2 | 30 |
2 | 3~6 | 70 |