7236번 - 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ą.

• 3 ≤ N ≤ 500 000
• 1 ≤ b_i, c_i ≤ N
• 1 ≤ K ≤ N
• 1 ≤ M ≤ 1 000 000
• 1 ≤ a_i ≤ 1 000 000