Description

jiangys is going hiking and needs to pack some clothes.

He has $n$ clothes, and the $i$-th one keeps him warm by $a_i$ points. He can choose to bring $1\sim n$ clothes to meet the weather for the next $m$ days.

Each day has different rules:

If $t_i = 1$, the total warmth of the clothes he wears that day must be at least $x_i$.

If $t_i = 2$, the total warmth must not exceed $x_i$.

Each day, he can pick some of the clothes he packed(but must wear, so at least one).

What's the smallest number of clothes he needs to bring to meet all day's rules? If it's impossible, output $-1$.

Input Format

First line: $n$, number of clothes.

Second line: $a_1 \sim a_n$, warmth of each clothes.

Third line: $m$, number of days.

Next $m$ lines: $t_i$ and $x_i$, rules for each day.

$1 \leq n \leq 3 , 1 \leq a_i \leq 2 \times 10^5, 1 \leq m \leq 100, 1 \leq t_i \leq 2,1 \leq x_i \leq 10^9$.

Output Format

The smallest number of clothes he needs to bring, or $-1$ if impossible.

Sample Input #1

3
2 3 5
1
1 10

Sample Output #1

3

Sample Input #2

3
2 3 5
2
1 5
2 2

Sample Output #2

2

Sample Input #3

3
7 11 13
2
1 24
2 7

Sample Output #3

3

Sample Input #4

2
17 19
2
1 16
2 18

Sample Output #4

1

Sample Input #5

3
2 11 19
2
1 1000000000
2 1

Sample Output #4

-1