Wallpaper

题意翻译

有 $n$ 个房间，$m$ 种墙纸，第 $i$ 个房间的长宽高分别是 $L_i$ $W_i$ $H_i$，第 $i$ 种墙纸的长宽价格分别是 $l_i$ $w_i$ $p_i$，每个房间的四周要贴上同种墙纸，多了也不能用到别的房间，墙纸可以裁剪但不能旋转，且首尾不能拼接（竖直方向必须是同一张墙纸，不能底下用第一张上面用第二张），问至少需要多少钱。

题目描述

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

1
5 5 3
3
10 1 100
15 2 320
3 19 500

输出样例 #1

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.