Clock Adjusting

The International Committee for Programmable Clocks (ICPC) recently ran into an absolutely catastrophic disaster. A member from their rivalry
— Advanced Clock Machinery (ACM) broke into ICPC’s headquarters! The security guards were quick to act but still unable to take him down before he shot at ICPC’s most valuable assets — clocks, with his powerful railgun. As a consequence, the hour hands on these clocks are now pointing to incorrect positions. You are now hired to help them salvage the clocks by restoring them to their initial states, which is 12 o’clock.

To formalize this problem, initially ICPC has $n (n \leq 8)$ clocks laid sequentially on your table, with hour hands pointing to arbitrary positions from 1 to 12.

You are given a set of $m$ tools $(m \leq 4)$. With tool $i$ (denoted by $(l_i, x_i)$), you can first choose a segment of $l_i$ clocks, then rotate their hour hands. If $x_i$ is positive, then tool $i$ rotates the hour hands by $x_i$ clockwise. If $x_i$ is negative, then tool $i$ rotates the hour hands by -$x_i$ counter-clockwise. The cost of using any tool is 1, and you may use the same tool more than once. However, you may rearrange the order of the clocks without any cost.

So now you are wondering: What is the minimum cost require to restore all the clocks?

Input contains multiple test cases. There will be no more than $60$ test cases. The first line in the input file contains a positive integer $T$, indicating the number of test cases to follow. Each test case starts with two integers $n$ and $m$ on the first line, where $1 \leq n \leq 8$ and $1 \leq m \leq 4$. $n$ is the number of clocks ICPC has and $m$ is the number of tools you have. You may assume that there are at most $45$ test cases containing $n = 8$, and the minimum costs are at most $8$ in at least two thirds of these test cases. The next line contains $n$ integers $h_1, . . . , h_n ∈ \{1, . . . , 12\}$, denoting where the hour hands are pointing to initially. The last $m$ lines provide information regarding the tools you have. The $i-th$ one contains two integers $l_i$ and $x_i$ where $1 \leq l_i \leq n$ and $-11 \leq x_i \leq 11$. The explanation of which are given in the problem description.

For each test case, output the minimum cost in a single line. If there is no solution or the answer is greater than $8$, output $-1$.

2
4 2
7 10 7 9
3 2
3 3
2 1
4 5
1 -1

2
-1

2015 ACM/ICPC Asia Regional Changchun Online