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]);
}
}
}
}