It's Valentine's day in Mackenzie City, which means Alice and Bob are going on a date frenzy!
There are date locations around Mackenzie City, labelled
to
. The couple wants to visit all the date locations in succession, going from date location
to
,
to
and so on.
Starting at date location and ending at location
, they will travel using the network of exactly
bi-directional bus routes connecting the date locations, such that it is possible to take some sequence of buses from any date location to another.
Each bus route has a single-use fare which needs to be re-purchased every time the couple travels along the route. Each bus route also has a multi-use fare
which can be purchased once, and all future travel on the route is free.
Since the couple would like to spend their money at the date locations rather than transiting, what is the minimum price they must pay for transit? Remember, it's two people!
Constraints
Input Specification
The first line of input will contain .
The next lines will contain
space-separated integers
representing a bi-directional bus route connecting date locations
and
with single-use fare
and multi-use fare
.
Output Specification
Output the minimum price Alice and Bob must pay for transit to visit all date locations in succession.
Sample Input
3
1 3 3 5
3 2 2 3
Sample Output
12
Explanation of Sample Input 1
The couple can buy two single-use fares for the bus route connecting date locations
and
and two
multi-use fares for the line connecting bus routes
and
for a total cost of
.
Comments