A	Rent a Car

The ACM (Advanced Car Management) Rent a Car company is very famous now-a-days because of their quality and service. Gaining popularity is not that easy as there are many competitor companies around. Each day they have a large number of car requests. Once a car is used for a day, if they want to use it later, they should send it for servicing. Actually it was their key theme for business and that's why they are so popular. There are C motor companies in town, where the k^th company has c_k cars in their showroom and price of a car of this company is p_k. There are R car service-centers in town, the i^th center takes d_i days and costs s_i per car service. Service centers can service huge number of cars at the same time. Now, ACM company has the request sheet for next N days, where in j^th day, r_j cars are needed. They want to fulfill all the requirements with minimized cost. Initially, ACM has empty garage. But their garage is huge and can store any number of cars.

Input

The first line of input will contain T (≤ 100) denoting the number of cases.

Each case starts with three integers N, C, R (1 ≤ N, C, R ≤ 50). The next line contains N integers where the j^th integer denotes r_j (0 ≤ r_j ≤ 100). The next line contains 2C integers where the k^th integer-pair denotes c_k and p_k (1 ≤ c_k, p_k ≤ 100). The next line contains 2R integers where the i^th integer-pair denotes d_i and s_i (1 ≤ d_i, s_i ≤ 100).

Output

For each case, print the case number and the minimized cost to fulfill all the requests. If it's impossible to do so, print "impossible".

Sample Input

Output for Sample Input

3 2 1

10 20 30

40 90 15 100

1 5

3 2 1

10 20 30

40 90 15 100

2 5

Case 1: 4650

Case 2: impossible

Note

For case 1, 50 cars will be bought, 40 from company 1 (costs 40*90=3600) and 10 from company 2 (costs 10*100=1000). On day 1, 10 cars will be sent and then they will be sent to the service center (costs 10*5=50). The cars will be received on day 3. On day 2, 20 cars will be sent. And on day 3, 20 unused cars will be sent along with the 10 cars (serviced). So, overall cost is 3600+1000+50 = 4650.

Problem Setter: Jane Alam Jan, Special Thanks: Antony Stabile, Derek Kisman