2350: Number Convertor

In this problem, you are given two positive integers,  a and b followed by n numbers c1,c2,c3..cn. Using four basic arithmetic operations (addition, subtraction, multiplication and division(use floor to reach an integer)) and only the given numbers, convert a into b. For instance suppose  a=2and b=10 and the numbers  are c1=2,c2=3 given to you. Two different ways to convert a to b are as follow:

1. First multiply a by c2, then add c1 to the result  for two times.

2. Add c1 to a ,  4 times.

There is just one more point that you should consider; different arithmetic operations have different costs. These costs are represented as a n*4 table, in which the cell (i,1),(i,2),(i,3),(i,4), of this table contains the cost of addition, subtraction, multiplication and division with ci as a second operand respectively. You should find the minimum cost to convert a to b such that you never reach a number more than 100000 and less than zero.

The number of test cases comes in the first line. For each test case, first there are three integer 1<=a,b<=100000 and 1<=n<=10. Then you are given n positive integer c1,c2,c3...cn . Finally, in the last  n lines in each line there are  4 positive integer that represent cost of operations.

For each test case, print the minimum cost to convert a to b  or IMPOSSIBLE, if we can not  convert a to b.

1
45 768 3
6 2 12
1 2 3 4
1 2 3 4
4 3 2 1

7