题目背景

一天，GD和MW正在玩一款名叫大海战的游戏。

题目描述

游戏在一个 $1 \times n$ 的棋盘上进行。一开始 GD 拥有 $c$ 种战舰，每种战舰的宽度为 $1$，长度为 $c_i$，共有 $t_i$ 个。GD 要将所有这些战舰放置在棋盘上，并且任意两艘战舰间不能重叠（但可以相邻）。

接下来，MW 进行 $q$ 次“攻击”，每次攻击一个 $1 \times 1$ 的格子，而 MW 将告知他这次攻击是否“打中”了一艘战舰（或者它的某个部分）。

令人疑惑的是，每次 MW 都告诉 GD 说他没有打中任何一艘战舰，而这显然是不现实的。现在 MW 把整个游戏的过程告诉了你，他想知道，最早在他的第几次询问之后，可以断定 GD 一定（至少有一次）说了谎。

输入格式

本题单测试点内有多组数据。

第一行一个整数 $t$，表示测试数据的组数。

每组数据的输入格式如下：

每组数据的第一行有三个整数，分别代表棋盘的长度 $n$ 、战舰的种数 $c$ 和攻击的次数 $q$。

对于每组数据的第 $2$ 到第 $(c + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的两个整数分别代表第 $i$ 种战舰的长度 $c_i$ 和数量 $t_i$。

第 $(c + 2)$ 行有 $q$ 个整数，第 $i$ 个整数 $a_i$ 代表 MW 第 $i$ 次攻击的位置。

输出格式

对于每组数据，输出一个整数 $ans$，表示最早在第 $ans$ 次操作后可以断定 GD 说了谎。特别地，如果一开始就不可能按要求摆上所有的战舰，输出 $0$；如果 $q$ 次询问后都不能判断 GD 是否说了谎，则输出 $-1$。

3
12 2 2
1 1
2 5
6 8
5 1 2
3 1
1 5
11 3 0
2 2
3 1
5 1

2
-1
0

提示

样例输入输出 1 解释

• 对于第一个样例，存在布阵 $\{1,22,22,0,22,22,22\}$（$0$ 表示没有放置），使得第一次不会受到攻击；不存在一个布阵使得两次都没有受到攻击。
• 对于第二个样例，存在布阵 $\{0,333,0\}$，使得两次均不会受到攻击。
• 对于第三个样例，一开始就不可能把所有战舰合法地布置在棋盘上。

数据规模与约定

• 对于测试点1，$n \leq 1000000000$，$c \leq 100000$，$q=0$；
• 对于测试点2、3，所有的 $t_i$ 均为 $1$；
• 对于测试点2-8，$n \leq 400000$，$c \leq 100$，$q=1$；
• 对于测试点9，$n \leq 100$，$c=1$，$q \leq 100$；
• 对于测试点10-14，$n \leq 200000$，$c=1$，$q \leq 200000$；
• 对于测试点15、16，$n \leq 200$，$c=2$，$q \leq 200$；
• 对于测试点17-20，$n \leq 4000$，$c=2$，$q \leq 4000$。
• 对于 $100\%$ 的数据，$1 \le t \le 5,n \ge 1,c \ge 1,q \ge 0,1 \le q_i \le n,0 \le c_i \le 10^5,0 \le t_i \le 10^5$。

提示

• 请注意常数因子对程序效率造成的影响。