Take Me Home (To the Place I Belong)

Input: Standard Input

Output: Standard Output

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 company’s 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 m_i(0< m_i<100000001) and p_i(0< p_i<10001) where m_i represents the size of the boxes and p_i represents the price of each box of that size. Then there will be N lines each containing 2 integer number n_i (0<n_i<100001) (represents the size of the objects that is required to pack) and r_i n_i (0<r_i<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 Output for 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

12 10

0 0 0

case 1: 1680

case 2: not possible

PS: Syed Monowar Hossain

Special Thanks: Abdullah al Mahmood, Shahriar Manzoor