The military parade will last for $n$ days. There is a aerobatic flight shows everyday during the parade. On the $i$th day , $P_i$ pilots are required. But the pilots are not willing to work continually without an extra salary for even two days , because they are extremely tired.
There are $m$ Holiday formulations in this country. For each formulation $j$ , that is: when a pilot works on a day , if you pay him $S_j$ dollars he is willing to come back $T_j$ days after that day.
For example , If a pilot work on the $r$th day , and $T_j==1$ then he will return to work on $r+1$th day
At the very beginning there are k pilots , but of course you can hire more pilots. However , training new pilots require $P$ days and for each new pilot you need pay him $Q$ dollars. (Which means you can only use new pilots on $P$th day or later)
Now our great king needs you to plan all these things. There must be enough pilots everyday and the cost must be minimized. Please tell the king what is the lowest cost;
Input
The first line contains a number $T(T \le 5)$, the number of testcases.
For each testcase, the first line contains a number $n (n \le 200)$
On the second line , there are n numbers $P_i(1 \le i \le n)$ indicating the number of pilots needed on that day
On the third line , 3 numbers , $m(1 \le m \le 5) , P , Q$
On the following m lines , each line has two numbers: $S_i$ , $T_i$
all input data $x$ satisfy $x\in[0 , 200]$
Output
For each testcase, print a single number. The minimum cost.
If there is no solution , just put `No solution`
