Due to a recent change in management, You're now the general manager for the Toronto Maple Leafs!
The National Hockey League (NHL) boasts of the world's best ice hockey players. The -th player wears jersey number and you've given the player a rating of .
The Toronto Maple Leafs are just one of the teams on the NHL. While they are a solid team, they fail each year at winning the championship trophy, the Stanley Cup. The Leafs roster currently has players wearing jersey numbers .
The NHL allows players to be traded across teams. Teams are always on the lookout for good players, and you've made a list of trade pairs indicating that any team would trade player for player or vice-versa. A trade may only happen if:
- is a trade pair in your list.
- is on a different team than .
We define the value of a team to be the sum of the ratings of the team's roster. In order to maximize the Leafs' chances of winning the Stanley Cup this year, can you determine the maximum value of the team given an unlimited (possibly none) amount of trades?
Constraints
For all subtasks,
All are distinct.
Each trade pair will only be stated once. Note that the trade pair is the same as the trade pair .
Subtask | Points | Constraints |
---|---|---|
It's possible to trade any player for another player through some sequence of trades. | ||
No additional constraints. |
Input Specification
The first line of input will contain space-separated integers , , and .
The second line will contain space-separated integers .
The third line will contain distinct space-separated integers .
The next lines will contain space-separated integers and indicating that is a trade pair.
Output Specification
Output one integer, the maximum value of the team after an unlimited (possibly none) amount of trades.
Sample Input
7 3 5
100 97 56 77 87 90 88
2 3 5
1 2
2 3
3 6
5 4
4 7
Sample Output
285
Explanation
The Leafs currently have players , , and and the team hs a value of . If we:
- Trade player for player (roster is now players , , and )
- Trade player for player (roster is now players , , and )
- Trade player for player (roster is now players , , and )
- Trade player for player (roster is now players , , and )
We can obtain a value of . It can be proven that this is maximal.
Comments