2021-03-22

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

public class Solution {

    private static final int MaxM = 200000;
    private static final long[] f = new long[MaxM + 3];
    //Map<K,V> k 为工作开始时间，V是集合--> 已K为开始时间的工作 的结束时间 集合
    private static final HashMap<Integer, ArrayList<Integer>> all = new HashMap<>();
    private static final int[][] fee = new int[2][103];
    private static StreamTokenizer in;
    private static int N, M, K, last;

    private static PriorityQueue<Integer> pq = new PriorityQueue<>();

    private static void init() {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    public static void main(String[] args) throws IOException {
        init();
        int T = nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = nextInt();
            M = nextInt();
            for (int i = 0; i < M; i++) {
                int s = nextInt();
                int e = nextInt();
                ArrayList<Integer> aList = all.getOrDefault(s, new ArrayList<>());
                aList.add(e);
                all.put(s, aList);
                last = Math.max(last, e);//所有工作的 最后结束时间
            }
            for (int i = 1; i <= K; i++) {
                fee[0][i] = nextInt();
                fee[1][i] = nextInt();
            }
            dp();
            long ans = 0;
            for (int i = 1; i <= last; i++) {
                if (all.containsKey(i)) {
                    pq.addAll(all.get(i));
                    while (!pq.isEmpty() && pq.peek() < i) pq.poll();//将结束的工作 清出PQ
                    if (pq.size() > N) ans += f[pq.size() - N];//当工作数大于N时，从f[i]取 最低费用
                }
            }
            System.out.println("#" + tc + " " + ans);
            for (ArrayList<Integer> val : all.values()) val.clear();
        }
    }
    //完全背包 动态规划
    private static void dp() {
        Arrays.fill(f, Long.MAX_VALUE >> 1);
        f[0] = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = fee[0][i]; j <= M; j++) {
                f[j] = Math.min(f[j], f[j - fee[0][i]] + fee[1][i]);
            }
        }
    }
}