Cheating Detection in Battleship Game

In this problem, you are given a \(1 \times n\) board and a set of battleships. Initially, GD places \(c\) types of battleships on the board. Each battleship has a width of \(1\) and a length of \(l_i\), and there are \(t_i\) copies of each type. The battleships must be placed so that they do not overlap (although they may touch).

After the placement, MW performs \(q\) attacks. Each attack targets one cell of the board and GD always responds that the attack missed every battleship. However, this response is suspicious since it may be impossible for all attacks to be misses.

Your task is to determine the smallest attack index after which it can be guaranteed that GD has lied at least once, i.e. there is no valid placement of all battleships on the board avoiding all attacked cells. If it is possible to have a valid placement after all attacks, output \(-1\).

inputFormat

The input is given as follows:

n
c
l1 t1
l2 t2
... 
lc tc
q
a1 a2 ... aq

Here, \(n\) is the length of the board. \(c\) denotes the number of battleship types. For each battleship type \(i\), \(l_i\) is the length of the battleship and \(t_i\) is the number of such ships. \(q\) is the number of attacks and \(a_j\) (1-indexed) is the attacked cell in the \(j\)-th attack.

outputFormat

Output a single integer representing the smallest attack index (1-indexed) after which it is impossible to place all battleships without covering any attacked cell. If a valid placement exists after all attacks, output \(-1\).

sample

10
1
3 2
3
2 5 8

2