Description

The game is played on a $1 \times n$ board. Initially, GD has $c$ types of ships. Each ship has width $1$, length $c_i$, and there are $t_i$ ships of the $i$-th type. GD must place all these ships on the board so that no two ships overlap (they may be adjacent).

Next, MW makes $q$ “attacks,” each time targeting a $1 \times 1$ cell, and GD will tell him whether that attack “hit” a ship (or any part of it).

Puzzlingly, GD tells MW every time that he did not hit any ship, which is clearly unrealistic. Now MW reveals the entire gameplay to you. He wants to know the earliest time, after which of his attacks, one can conclude that GD must have lied at least once.

Input Format

There are multiple test cases within a single test file.

The first line contains an integer $t$, the number of test cases.

For each test case:

• The first line contains three integers, the board length $n$, the number of ship types $c$, and the number of attacks $q$.
• The next $c$ lines (lines $2$ to $(c + 1)$) each contain two integers. On line $(i + 1)$, the two integers are the length $c_i$ and the count $t_i$ of the $i$-th type of ship.
• Line $(c + 2)$ contains $q$ integers. The $i$-th integer $a_i$ is the position targeted by MW’s $i$-th attack.

Output Format

For each test case, output a single integer $ans$, the earliest index such that after the $ans$-th operation you can conclude GD has lied. In particular, if it is impossible from the very beginning to place all ships as required, output $0$. If after all $q$ attacks you still cannot determine whether GD has lied, output $-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

Hint

• Sample Input/Output 1 Explanation:

  • For the first sample, there exists a layout $\{1,22,22,0,22,22,22\}$ ($0$ means empty) such that the first attack misses; no layout can make both attacks miss.
  • For the second sample, there exists a layout $\{0,333,0\}$ such that both attacks miss.
  • For the third sample, it is impossible to place all ships legally from the start.

• Constraints:

  • For test point 1, $n \leq 1000000000$, $c \leq 100000$, $q = 0$.
  • For test points 2–3, all $t_i$ are $1$.
  • For test points 2–8, $n \leq 400000$, $c \leq 100$, $q = 1$.
  • For test point 9, $n \leq 100$, $c = 1$, $q \leq 100$.
  • For test points 10–14, $n \leq 200000$, $c = 1$, $q \leq 200000$.
  • For test points 15–16, $n \leq 200$, $c = 2$, $q \leq 200$.
  • For test points 17–20, $n \leq 4000$, $c = 2$, $q \leq 4000$.
  • For $100\%$ of the testdata, $1 \le t \le 5, n \ge 1, c \ge 1, q \ge 0, 1 \le a_i \le n, 0 \le c_i \le 10^5, 0 \le t_i \le 10^5$.

• Note: Please be mindful of the impact of constant factors on performance.

Translated by ChatGPT 5