cities are connected by roads in the most efficient way possible, with at most 1 road between any two cities. Since loves to go on dates with across his entire empire, he built roads such that it is possible to go from one city to any other. Every city has a bus station that can drive up to cities away, at the price of .
is going on vacation with the love of his life, ! is touring in his favourite country, the Antartic Empire. His, and end at another city. Specifically, at city , will get off the bus, visit , and then get back on a second bus. It is guaranteed that city is not a leaf node (city with 1 road). also enjoys taking long walks on the beach long tours, so he will only choose tours that start and end on a leaf node. In addition, he will not choose any tours that goes through any city twice, to minimize his chances of contracting the coronavirus. defines a tour to "go through" a city if on his tour, a bus starts/stops at the city, or the bus drives through a city.
Unfortunately for
, has shattered his refuge in Antarctica and taken all his money, so must borrow money from to fund their tour. He would like to borrow as little money as possible from so he doesn't get dumped. Please help find the minimum possible cost!Input Specification
The first line will contain , the number of cities in the Antartic Empire, and 's hometown.
The next lines will contain 2 integers , meaning that cities and are connected by a road.
The next line will contain integers , meaning the city's bus station can drive cities away.
The next line will contain integers , the price of using the city's bus station.
Output Specification
The minimum cost of
's tour across the Antartic Empire.Subtasks
Subtask 1 [40%]
Subtask 2 [60%]
No further constraints.
Sample Input
7 1
1 2
1 3
2 4
2 5
3 6
3 7
1 3 2 4 3 5 6
2 3 5 2 3 1 3
Sample Output
6
Explanation for Sample
, goes to city with a cost of , then goes to city with a cost of , then goes to city with a cost of , adding up to a total cost of .
first starts at city
Comments