# Great Equipment

Time Limit: Java: 10000 ms / Others: 10000 ms

Memory Limit: Java: 32768 KB / Others: 32768 KB

## Input

The input describes several test cases. The first line of input for each test case contains a single integer n, the number of trade caravans (0 <= n <= 100). The following four lines describe the information of those equipments. The first line contains three integers w1, s1 and d1, indicating the weight, size and defend capabilities of the helm. The integers w2, s2 and d2 in the second line represent the weight, size and defend capabilities of the armor. Also, in the third line, w3, s3 and d3 are the weight, size and defend capabilities of the boot. The fourth line contains four integers c1, c2, c3 and d4. Among those integers, c1, c2, c3 are the number of helms, armors and boots in a set of equipments, d4 is the capability of this set. In the test case, following those data are n lines, describing the carrying capabilities of the trade caravans. Each line contains two integers, xi and yi, indicating the weight limit and size limit of a trade caravan. The input is terminated by a description starting with n = 0. This description should not be processed. Note: Because of the trade caravans' carrying capabilities, you may assume the quantities of the helms, armors and boots will not exceed 500 respectively.

## Output

Your program must compute the defend capability of the best carrying plan. That is, after having performed the carrying plan, the defend capability of the equipments which have been carried away from the castle should be the largest. For each test case in the input file, print the case number and a colon, and then the defend capability of those equipments. Print a blank line between test cases.

## Sample Input

3
1 1 3
5 6 10
2 1 2
1 1 1 50
1 1
5 6
2 1
0

## Sample Output

Case 1: 50

None

## Source

Asia 2001, Shanghai (Mainland China)