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 ck cars in their showroom and price of a car of this company is pk. There are R car service-centers in town, the i-th center takes di days and costs si 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, rj 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 rj (0 ≤ rj ≤ 100). The next line contains 2C integers where the k-th integer-pair denotes ck and pk (1 ≤ ck,pk ≤ 100). The next line contains 2R integers where the i-th integer-pair denotes di and si (1 ≤ di, si ≤ 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’. 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. Sample Input 2 321 10 20 30 40 90 15 100 15 321 10 20 30 40 90 15 100 25 Sample Output Case 1: 4650 Case 2: impossible