Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Wallpaper

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHaving 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.

Input

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.

Output

Print a single number — the minimum total cost of the rolls.

Examples

Input

1

5 5 3

3

10 1 100

15 2 320

3 19 500

Output

640

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2018 20:29:48 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|