4002: Wallpaper
Description
Having bought his own apartment, Boris decided to paper the walls in every room. Boris's flat has n rooms, each of which has the form of a rectangular parallelepiped. For every room we known its length, width and height of the walls in meters (different rooms can have different dimensions, including height).
Boris chose m types of wallpaper to paper the walls of the rooms with (but it is not necessary to use all the types). Each type of wallpaper is sold in rolls of a fixed length and width (the length, naturally, shows how long the unfolded roll will be). In addition, for each type we know the price of one roll of this type.
The wallpaper of each type contains strips running along the length of the roll. When gluing the strips must be located strictly vertically (so the roll cannot be rotated, even if the length is less than the width). Besides, a roll can be cut in an arbitrary manner, but the joints of glued pieces should also be vertical. In addition, each room should be papered by only one type of wallpaper. And pieces of the same roll cannot be used to paper different rooms. That is, for each room the rolls are purchased separately. Also, some rolls can be used not completely.
After buying an apartment Boris is short of cash, so he wants to spend the minimum money on wallpaper. Help him.
The first line contains a positive integer n (1≤n≤500) − the number of rooms in Boris's apartment.
Each of the next n lines contains three space-separated positive integers − the length, width and height of the walls in a given room in meters, respectively.
The next line contains a positive integer m (1≤m≤500) − the number of available wallpaper types.
Each of the following m lines contains three space-separated positive integers − the length and width in meters of a given wallpaper and the price of one roll, respectively.
All numbers in the input data do not exceed 500. It is guaranteed that each room can be papered using these types of wallpaper.
Print a single number − the minimum total cost of the rolls.
1
5 5 3
3
10 1 100
15 2 320
3 19 500
640
Note to the sample:
The total length of the walls (the perimeter) of the room is 20 m.
One roll of the first type can be cut into pieces to get three vertical 1 meter wide strips, ergo you need 7 rolls of this type, the price equals 700.
A roll of the second type can be cut into pieces to get five 2 meter wide strips, we need 2 rolls, the price is 640.
One roll of the third type can immediately paper 19 meters out of 20, but we cannot use other types and we have to buy a second roll, the price is 1000.