**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**