小红的双生英雄

import java.util.*;

// 双生英雄捆绑在1个下标i, 4种情况取min： 不选、选1个、都选(触发额外加成)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), c = in.nextInt(), m = in.nextInt();
        int[] a = new int[n], b = new int[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt(); // cost
            b[i] = in.nextInt(); // attack
        }
        Map<Integer, int[]> link = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int u = in.nextInt() - 1, v = in.nextInt() - 1, w = in.nextInt();
            link.put(u, new int[] {v, w});
            link.put(v, new int[] {u, w});
        }

        int[][] heros = new int[n - m][5]; // 整合英雄 {cost1, atk1, cost2, atk2, w}
        boolean[] used = new boolean[n];
        for (int i = 0, k = 0; i < n; i++) {
            if (used[i]) continue;
            if (link.containsKey(i)) {
                int[] arr = link.get(i);
                int u = i, v = arr[0], w = arr[1];
                heros[k] = new int[] {a[u], b[u], a[v], b[v], w}; // 双生英雄
                used[v] = true;
            } else {
                heros[k] = new int[] {a[i], b[i], INF, 0, 0}; // 单个英雄：cost2置INF表示不可达
            }
            k++;
        }

        long[][][] dp = new long[4 + 1][n - m + 1][c + 1]; // long：结果会很大
        for (int k = 1; k <= 4; k++) {
            for (int i = 1; i <= n - m; i++) {
                int[] h = heros[i - 1];
                int a1 = h[0], b1 = h[1], a2 = h[2], b2 = h[3], w = h[4];
                for (int j = 1; j <= c; j++) {
                    long res = dp[k][i - 1][j]; // 不选
                    if (j >= a1) { // 选英雄1
                        res = Math.max(res, dp[k - 1][i - 1][j - a1] + b1);
                    }
                    if (j >= a2) { // 选英雄2
                        res = Math.max(res, dp[k - 1][i - 1][j - a2] + b2);
                    }
                    if (j >= a1 + a2 && k >= 2) { // 都选+额外奖励
                        res = Math.max(res, dp[k - 2][i - 1][j - a1 - a2] + b1 + b2 + w);
                    }
                    dp[k][i][j] = res;
                }
            }
        }
        System.out.println(dp[4][n - m][c]);
    }
    private final static int INF = Integer.MAX_VALUE / 2;
}