Vagys

문제

Bitlandijoje yra N miestų, sunumeruotų nuo 1 iki N, kuriuos jungia N −1 kelias taip, kad iš bet kurio miesto galima vieninteliu būdu nukeliauti į bet kurį kitą.

Vagių grupė įvykdė didžiausią nusikaltimą Bitlandijos istorijoje – vienu metu apvogė parduotuves K skirtingų miestų. Kadangi nusikaltimas įvykdytas neseniai, jie dar nespėjo pabėgti į kitus miestus, bet manoma, kad jie gali taip daryti. Tai žinodama, policija gali greitai užtverti įvažiavimus į kai kuriuos miestus (išvažiavimo iš miesto užtverti negalima) – tokiu būdu jie apribos nusikaltėlių judėjimą, nes žinos, kad į tą miestą vagys įvažiuoti negalėjo. Po to jie apieškos visus miestus, kuriuose vagys gali būti.

Deja, policijos resursai ne begaliniai, o bet kokia veikla kainuoja pinigus. Bet kurį miestą apieškoti kainuoja M pinigų, o užtverti visus kelius į i-tąjį miestą kainuoja a_i pinigų. Policija nori parinkti uždaromus miestus (t. y. į kuriuos uždarys kelius) taip, kad visa paieškos operacija kainuotų kuo mažiau.

Raskite, kiek mažiausiai gali kainuoti paieškos operacija.

입력

Pirmoje eilutėje pateikti trys sveikieji skaičiai: N – Bitlandijos miestų skaičius, K – miestų, kuriuose įvykdytos vagystės, skaičius ir M – miesto apieškojimo kaina.

Tolesnėse N − 1 eilutėje pateikta po du tarpu atskirtus sveikuosius skaičius b_i ir c_i – miestų, kuriuos jungia i-tas kelias, numeriai.

Po to esančioje eilutėje yra N sveikųjų skaičių, i-tas jų yra a_i – įvažiavimų į i-tąjį miestą užtvėrimo kaina.

Paskutinėje eilutėje yra K sveikųjų skaičių – miestų, kuriuose įvykdytos vagystės, numeriai.

출력

Išveskite vienintelį skaičių – mažiausią galimą paieškos operacijos kainą.

6 3 2
1 2
2 3
2 4
4 5
5 6
1 3 2 1 3 1
1 4 6

11