Question
Maximum Gold Collection in a Kingdom
You are exploring a kingdom made up of KaTeX can only parse string typed expression cities connected by roads. Each city contains a certain amount of gold, but you can collect the gold from a city only the first time you visit it.
The kingdom is represented as an undirected graph:
-
Each city is a node.
-
Each road connects two cities and can be traveled in both directions.
You may start your journey from any city of your choice. From there, you can move to any adjacent connected city, and you are allowed to visit the same city multiple times, but gold is collected only once per city.
Your task is to determine the maximum total gold you can collect by choosing an optimal starting city and moving through the kingdom.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of cities and roads.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression, where KaTeX can only parse string typed expression is the amount of gold in city KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning there is a road between city KaTeX can only parse string typed expression and city KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression, where KaTeX can only parse string typed expression is the amount of gold in city KaTeX can only parse string typed expression.
The next KaTeX can only parse string typed expression lines each contain two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning there is a road between city KaTeX can only parse string typed expression and city KaTeX can only parse string typed expression.
Output
Print a single integer — the maximum gold that can be collected if you start your journey from any city of your choice.
Example
Input
5 3
1 2 3 3 4
1 2
2 3
4 5
Output
7
Explanation
The gold collected on the Journey Node 1 --> Node 2 --> Node 3 is:
1 + 2 + 3 = 6
However, the optimal journey is:
Node 4 --> Node 5
Gold collected = 3 + 4 = 7
5 3
1 2 3 3 4
1 2
2 3
4 5
Output
7
Explanation
The gold collected on the Journey Node 1 --> Node 2 --> Node 3 is:
1 + 2 + 3 = 6
However, the optimal journey is:
Node 4 --> Node 5
Gold collected = 3 + 4 = 7