Goods Transportation

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Truck is one of the main utilities for transporting goods and the carrying capacity varies among trucks. One day, a factory wants to transport four kinds of goods from one place to another. Each kind of goods has been made up into bags. In order to enlarge the profits as much as possible, the manager try to make a schedule by which the factory can have the most value of goods transported and thus achieve the minimum costs. Now, you, as an excellent programmer in the factory, are assigned to calculate the maximum value of total goods that the all trucks can transport in one run.

Input

The input may have several test cases. Each test case consists of seven lines. The first line of each test case is a number N (1 <= N <= 100), which shows the number of trucks the factory has. The second line has N numbers. The ith number of this line indicates the carrying capacity of the ith truck. There are 4 lines following the second line. Each of these four lines has two numbers, Wi and Vi, which shows the weight and value of a bag for one kind of goods. Because the first three kinds of goods can be made into a new kind, so the last line of each test cases has 4 numbers A, B, C and V, where A, B and C shows that the numbers of bags it needs from the first three kinds to make one bag of new kind, and V indicates the value of one bag of new kind. You may assume the number of bags of each kind will be always less than 100.

Process to the end-of-file.

Output

For every test case, there is one-line output and the output consists of exact one number, which is the total value of goods that all trucks can transport exactly in one run.

Sample Input

4
2 3 4 5
2 3
3 4
4 5
5 10
1 1 1 15

Sample Output

25

Submit

Source: ZOJ Monthly, March 2004