44 lines
808 B
Python
44 lines
808 B
Python
import sys
|
|
input = sys.stdin.readline
|
|
|
|
N, M, K = map(int, input().split())
|
|
|
|
candys = [0] + list(map(int, input().split()))
|
|
counts = [1] * (N+1)
|
|
parents = [i for i in range(N+1)]
|
|
|
|
def find(x) :
|
|
if parents[x] != x :
|
|
parents[x] = find(parents[x])
|
|
return parents[x]
|
|
|
|
def union(x, y) :
|
|
x = find(x)
|
|
y = find(y)
|
|
|
|
if x == y :
|
|
return
|
|
|
|
if x > y :
|
|
x, y = y, x
|
|
|
|
parents[y] = x
|
|
candys[x] += candys[y]
|
|
counts[x] += counts[y]
|
|
|
|
for _ in range(M) :
|
|
u, v = map(int, input().split())
|
|
union(u, v)
|
|
|
|
items = []
|
|
for i in range(1, N+1) :
|
|
if i == parents[i] :
|
|
items.append((counts[i], candys[i]))
|
|
|
|
dp = [0] * K
|
|
|
|
for weight, value in items :
|
|
for w in range(K-1, weight-1, -1) :
|
|
dp[w] = max(dp[w], dp[w-weight] + value)
|
|
|
|
print(dp[K-1]) |