题解 | 小红的双生英雄

import sys
input = sys.stdin.readline

n, C, m = map(int, input().split())
heroes = [tuple(map(int, input().split())) for _ in range(n)]

paired = set()
pair_info = []

for _ in range(m):
    u, v, bonus = map(int, input().split())
    u -= 1
    v -= 1
    pair_info.append((u, v, bonus))
    paired.add(u)
    paired.add(v)

# 单人英雄索引
singles = [i for i in range(n) if i not in paired]

# dp[k][c] = 选k人，总cost为c的最大战斗力，初始-1表示不可达
dp = [[-1] * (C + 1) for _ in range(5)]
dp[0][0] = 0

max_ans = 0  # 实时维护最大值

# --- 处理单人英雄 ---
for idx in singles:
    cost, power = heroes[idx]
    for k in range(3, -1, -1):
        for c in range(C - cost, -1, -1):
            if dp[k][c] != -1:
                new_val = dp[k][c] + power
                if new_val > dp[k + 1][c + cost]:
                    dp[k + 1][c + cost] = new_val
                    if new_val > max_ans:
                        max_ans = new_val

# --- 处理双生组合英雄 ---
for u, v, bonus in pair_info:
    cu, pu = heroes[u]
    cv, pv = heroes[v]

    combos = []
    if cu <= C:
        combos.append((1, cu, pu))
    if cv <= C:
        combos.append((1, cv, pv))
    if cu + cv <= C:
        combos.append((2, cu + cv, pu + pv + bonus))

    dp_old = [row[:] for row in dp]

    for people, cost, power in combos:
        max_k = 4 - people
        for k in range(max_k, -1, -1):
            for c in range(C - cost, -1, -1):
                if dp_old[k][c] != -1:
                    new_val = dp_old[k][c] + power
                    if new_val > dp[k + people][c + cost]:
                        dp[k + people][c + cost] = new_val
                        if new_val > max_ans:
                            max_ans = new_val

# --- 输出最大值 ---
print(max_ans)