LCC '22 Contest 2 J5 - Be-leaf-ing in the Leafs

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.4s
Memory limit: 256M

Author:
Problem type

Due to a recent change in management, You're now the general manager for the Toronto Maple Leafs!

The National Hockey League (NHL) boasts N of the world's best ice hockey players. The i \ (1 \le i \le N)-th player wears jersey number i and you've given the player a rating of a_i.

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 K players wearing jersey numbers b_1, b_2,..., b_K.

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 M trade pairs (x, y) indicating that any team would trade player x for player y or vice-versa. A trade may only happen if:

  1. (x, y) is a trade pair in your list.
  2. x is on a different team than y.

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,

1 \le K \le N \le 10^5

0 \le M \le 10^5

1 \le a_i \le 10^4

1 \le b_i, x, y \le N

x \ne y

All b_i are distinct.

Each trade pair (x, y) will only be stated once. Note that the trade pair (x, y) is the same as the trade pair (y, x).

SubtaskPointsConstraints
1100 \le M \le 1
220It's possible to trade any player x for another player y through some sequence of trades.
370No additional constraints.

Input Specification

The first line of input will contain 3 space-separated integers N, K, and M.

The second line will contain N space-separated integers a_1, a_2,..., a_N.

The third line will contain K distinct space-separated integers b_1, b_2,..., b_K.

The next M lines will contain 2 space-separated integers x and y indicating that (x, y) 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 2, 3, and 5 and the team hs a value of 97 + 56 + 87 = 240. If we:

  1. Trade player 2 for player 1 (roster is now players 1, 3, and 5)
  2. Trade player 3 for player 2 (roster is now players 1, 2, and 5)
  3. Trade player 5 for player 4 (roster is now players 1, 2, and 4)
  4. Trade player 4 for player 7 (roster is now players 1, 2, and 7)

We can obtain a value of 100 + 97 + 88 = 285. It can be proven that this is maximal.


Comments

There are no comments at the moment.