At last, eminent scientist Safdar Ali has decided to return to his beloved homeland Bangladesh after 16 years of exile in USA. As a scientist, he has many inventions and wants to bring back all those things he invented with him. He has already arranged them in groups of different sizes and wants some boxes to put them into and hand over the boxes to transport company. So he asked a company named “Pack-em-up Pvt. Ltd” to supply some boxes. But the companys policy is little bit tricky. They offer n different types of boxes, ranging from 1 to 1000000000 of various prices. For each type of boxes they can supply as many as the customer asks. But for each type of box, the company adds another C dollar with the total cost. So if Safdar Ali wants 3 different types of boxes, he has to pay the price for each box and extra 3 ∗ C dollar. To minimize the cost, Safdar is willing to buy larger boxes to fit smaller objects. So, Safdar Ali wants to buy the required boxes with minimum cost. Input There will be several test cases. For each test case, the first line contains 3 numbers: C, M and N, where C (0 ≤ C ≤ 10000) represents the extra cost that will be added for each type of boxes, M (0 < M < 1001) represents the number of types of boxes offered by the “Pack-em-up” Company, and N (0 < N < 1001) represents the number of types of boxes required by Safdar Ali. After that there will be M lines, each containing two integers mi (0 < mi < 100000001) and pi (0 < pi < 10001) where mi represents the size of the boxes and pi represents the price of each box of that size. Then there will be N lines each containing 2 integer number ni (0 < ni < 100001) (represents the size of the objects that is required to pack) and ri (0 < ri < 1001) (which represents the number of boxes that are required of that type). Input will be terminated when C = M = N = 0. Output For each test case, there will be one line of output. First print the test case number (see the sample output) and then the minimum costs to pack all of the objects. If it is not possible to pack, your output should be ‘not possible’. Sample Input 1000 4 3 5 10 7 12 9 15 11 17 1 10 2 20 10 10 100 4 3 5 10 7 12 9 15 10 17 1 10 2 20
2/2 12 10 000 Sample Output case 1: 1680 case 2: not possible