L. Clothes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Xiao Ming 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 days' rules? If it's impossible, output $$$-1$$$.

Input

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 \le n \le 3$$$, $$$1 \le a_i \le 2 \times 10^5$$$, $$$1 \le m \le 100$$$, $$$1 \le t_i \le 2$$$, $$$1 \le x_i \le 10^9$$$.

Output

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

Examples
Input
3
2 3 5
1
1 10
Output
3
Input
3
2 3 5
2
1 5
2 2
Output
2
Input
3
7 11 13
2
1 24
2 7
Output
3