import sys from collections import deque def solve(): input = sys.stdin.read().split() ptr = 0 n, m, W = map(int, input[ptr:ptr+3]) ptr +=3 items = [] for _ in range(n): w, v = map(int, input[ptr:ptr+2]) items.append((w, v)) ptr +=2 adj = [[] for _ in range(n+1)] in_degree = [0]*(n+1) for _ in range(m): x, y, z = map(int, input[ptr:ptr+3]) adj[x].append((y, z)) in_degree[y] +=1 ptr +=3 # Topological sort q = deque() for u in range(1, n+1): if in_degree[u] ==0: q.append(u) topo_order = [] while q: u = q.popleft() topo_order.append(u) for (v, z) in adj[u]: in_degree[v] -=1 if in_degree[v] ==0: q.append(v) # DP[u][w] = (max_value, min_energy) dp = [ [ (-1, float('inf')) for _ in range(W+1) ] for _ in range(n+1) ] dp[1][0] = (0, 0) for u in topo_order: for w_u in range(W+1): if dp[u][w_u][0] == -1: continue current_value, current_energy = dp[u][w_u] for (v, z) in adj[u]: # Option 1: not take u's item new_w = w_u new_value = current_value new_energy = current_energy + w_u * z if new_value > dp[v][new_w][0]: dp[v][new_w] = (new_value, new_energy) elif new_value == dp[v][new_w][0]: if new_energy < dp[v][new_w][1]: dp[v][new_w] = (new_value, new_energy) # Option 2: take u's item if possible w_item, v_item = items[u-1] if w_u + w_item <= W: new_w = w_u + w_item new_value = current_value + v_item new_energy = current_energy + new_w * z if new_value > dp[v][new_w][0]: dp[v][new_w] = (new_value, new_energy) elif new_value == dp[v][new_w][0]: if new_energy < dp[v][new_w][1]: dp[v][new_w] = (new_value, new_energy) max_value = -1 min_energy = float('inf') for w in range(W+1): if dp[n][w][0] > max_value: max_value = dp[n][w][0] min_energy = dp[n][w][1] elif dp[n][w][0] == max_value: if dp[n][w][1] < min_energy: min_energy = dp[n][w][1] print(max_value, min_energy) solve()