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
.
, 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
.
Comments