CF139B.Wallpaper

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.

购买了自己的公寓后，鲍里斯决定为每个房间的墙壁贴壁纸。鲍里斯的公寓共有 $n$ 个房间，每个房间均为长方体形状。对于每个房间，我们已知其长、宽和墙高（单位：米）（不同房间的尺寸可能不同，包括高度）。

鲍里斯选定了 $m$ 种壁纸来装饰房间的墙壁（但并非必须使用全部种类）。每种壁纸均以固定长度和宽度的卷筒形式出售（其中“长度”自然表示卷筒展开后的长度）。此外，对于每种壁纸，我们还知道其单卷的价格。

每种壁纸的卷筒上印有沿卷筒长度方向延伸的条纹。粘贴时，这些条纹必须严格垂直（因此卷筒不可旋转，即使其长度小于宽度亦然）。此外，卷筒可被任意裁剪，但拼接处也必须保持垂直。另外，每个房间只能使用一种壁纸；同一卷筒中的壁纸不可用于装饰不同的房间，即每个房间所需壁纸需单独购买卷筒。同时，部分卷筒可能不会被完全用完。

购房后鲍里斯手头资金紧张，因此他希望在壁纸上花费最少的钱。请帮助他。

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.

第一行包含一个正整数 $n$（$1 \leq n \leq 500$）—— 表示鲍里斯公寓中的房间数量。

接下来的 $n$ 行，每行包含三个以空格分隔的正整数——分别表示对应房间的墙壁长度、宽度和高度（单位：米）。

下一行包含一个正整数 $m$（$1 \leq m \leq 500$）—— 表示可选壁纸类型的数量。

接下来的 $m$ 行，每行包含三个以空格分隔的正整数——分别表示某种壁纸的长度（米）、宽度（米）以及一卷的价格。

输入数据中的所有数字均不超过 500。保证每个房间均可使用所给的壁纸类型完成贴墙纸。

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

输出一个整数——掷骰子的最小总成本。

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.

样例说明：

房间墙壁的总长度（即周长）为 20 米。

第一种壁纸每卷可裁剪成三段宽 1 米的竖直条，因此需要 7 卷，总价为 700。

第二种壁纸每卷可裁剪成五段宽 2 米的条，因此需要 2 卷，总价为 640。

第三种壁纸每卷可直接覆盖 20 米中的 19 米，但由于不能混用其他类型，必须再购买一卷，总价为 1000。