## DMOPC '20 Contest 7 P5 - Mayors and Tolls

View as PDF

Points: 20
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You are trying to make a profitable business from toll roads. There are currently bidirectional roads between cities, the -th road connecting cities and . If you are able to turn the -th road into a toll road, you will gain a profit of .

However, you will only be able to buy a road between cities and if you have the approval of both mayors of the two cities. To gain the approval of the mayor of city , you can pay them a "fee" of cost . Once you have paid this "fee," the mayor will do their part to approve all roads neighbouring their city.

Overall, your net profit will be the sum of the profits from the roads minus the sum of the fees. What is the optimal net profit?

#### Input Specification

The first line contains integers and .

The second line contains integers .

The next lines each contain integers , , and .

#### Output Specification

Output the optimal net profit.

#### Sample Input

4 5
8 4 1 2
1 2 3
2 3 5
1 3 4
3 4 2
4 2 2

#### Sample Output

2