大海战
题目背景
一天,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$。
输入输出样例
输入样例 #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
输出样例 #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$。
---
#### 提示
- 请注意常数因子对程序效率造成的影响。