'''
先用并查集缩点,然后进行01背包DP
'''
import sys
sys.setrecursionlimit(99999999)
class MergeSetExt:
def __init__(self, max_key_val = 0, trans_key_func=None):
if trans_key_func is not None and max_key_val > 0:
# 如果能够提供转换key的回调,并查集内部用线性表存储
self.trans_key_callback = trans_key_func
self.m = [-1 for _ in range(max_key_val+1)]
self.__root2cluster_size = [0 for _ in range(max_key_val+1)]
else:
# 如果不能提供转换key的回调,并查集内部用hash表存储
self.trans_key_callback = None
self.m = {}
self.__root2cluster_size = {}
self.__root_cnt = 0
def getRoot(self, node):
buf = []
root = self.trans_key_callback(node) if self.trans_key_callback else node
while self.m[root] != root:
buf.append(root)
root = self.m[root]
for key in buf:
self.m[key] = root
return root
def merge(self, a, b):
orig_a, orig_b = a, b
if self.trans_key_callback:
a, b = self.trans_key_callback(a), self.trans_key_callback(b)
for node in [a, b]:
if (self.trans_key_callback is None and node not in self.m) or (self.trans_key_callback is not None and self.m[node] == -1):
self.m[node] = node
self.__root2cluster_size[node] = 1
self.__root_cnt += 1
root1 = self.getRoot(orig_a)
root2 = self.getRoot(orig_b)
if root1 != root2:
self.m[root1] = root2
self.__root2cluster_size[root2] += self.__root2cluster_size[root1]
if self.trans_key_callback:
self.__root2cluster_size[root1] = 0
else:
self.__root2cluster_size.pop(root1)
self.__root_cnt -= 1
# 根据根节点的数值获取其所在的簇的大小
def getClusterSize(self, root):
return self.__root2cluster_size[root]
def isInSameSet(self, a, b):
if a == b:
return True
orig_a, orig_b = a, b
if self.trans_key_callback:
a, b = self.trans_key_callback(a), self.trans_key_callback(b)
for node in [a, b]:
if self.m[node] == -1:
return False
else:
for node in [orig_a, orig_b]:
if node not in self.m:
return False
return self.getRoot(orig_a) == self.getRoot(orig_b)
def getRootNum(self):
return self.__root_cnt
def getClusters(self):
rec = {}
if self.trans_key_callback is None:
for node in self.m:
root = self.getRoot(node)
if root not in rec:
rec[root] = []
rec[root].append(node)
else:
for node in range(len(self.m)):
if self.m[node] == -1:
continue
root = self.getRoot(node)
if root not in rec:
rec[root] = []
rec[root].append(node)
return [nodes for nodes in rec.values()]
n, m, w = map(int, input().split())
val = [0] * (n+1)
cost = [0] * (n+1)
for i in range(1, n+1):
s = sys.stdin.readline()
cost[i], val[i] = map(int, s.split())
merge_set = MergeSetExt(max_key_val=n, trans_key_func=lambda x : x)
for i in range(1, n+1):
merge_set.merge(i, i)
for i in range(m):
s = sys.stdin.readline()
a, b = map(int, s.split())
merge_set.merge(a, b)
ans = 0
arr = []
for cluster in merge_set.getClusters():
total_cost, total_val = 0, 0
for node in cluster:
total_cost += cost[node]
total_val += val[node]
if total_cost <= w:
arr.append((total_cost, total_val))
# 01 背包
if len(arr) == 0:
print(0)
else:
dp = [0] * (w + 1)
for i in range(len(arr)):
for j in range(w, -1, -1):
if i == 0:
dp[j] = arr[i][1] if j >= arr[i][0] else 0
else:
if j >= arr[i][0]:
dp[j] = max(dp[j], arr[i][1] + dp[j - arr[i][0]])
print(dp[w])