E – Water Boy

Problem

A company that installs water dispensers in offices, homes, and shops, contacted you to solve their particular, tricky, distribution problem.

Water-replacement bottles come in three different sizes and are usually transported in mounting racks attached to the distribution trucks. Obviously, the sum of the bottle diameters on each rack cannot exceed the truck’s total width. Your goal is to maximize the amount of water transported by a truck.

The height of the bottles is such that the capacity of each bottle (in liters) corresponds to the same number of centimeters in its diameter, so that a bottle with 50 cm diameter holds exactly 50 liters.

Therefore, if we consider a truck that is 70cm wide with 2 racks, and we have three bottles 35cm wide and four bottles 20cm wide, the maximum load would be 130 liters. One possible solution in such a scenario would be to place two 35cm bottles (70 liters) in one rack and three 20cm bottles (60 liters) in the other rack.

Input

The input will consist of a non-negative integer indicating the width of the truck in centimeters, a positive integer indicating the number of racks in the truck, followed by three lines, one for each kind of bottle. On each of these lines there is a non-negative integer that determines the number of available bottles of that kind, and a positive integer indicating the corresponding diameter. The total number of bottles will not exceed 250, and the total number of racks is less or equal to 10.

Output

The output consists of an integer indicating the maximum number of liters of water that can be transported in the truck.

Sample Input

120

3

3 50

3 40

3 30

Sample Output

360