← 返回题目列表

Codeforces · 139/B

B. 壁纸

中文机器翻译题面 查看原题

购买了自己的公寓后,鲍里斯决定在每个房间的墙壁上贴上墙纸。鲍里斯的公寓有 n 个房间,每个房间的形状都是长方体。对于每个房间,我们都知道墙壁的长度、宽度和高度(以米为单位)(不同的房间可以有不同的尺寸,包括高度)。

鲍里斯选择了 m 种壁纸来装饰房间的墙壁(但不必使用所有类型)。每种类型的壁纸均以固定长度和宽度的卷形式出售(长度自然表明展开卷的长度)。此外,对于每种类型,我们都知道该类型一卷的价格。

每种类型的壁纸均包含沿着卷筒长度延伸的条带。粘合时,条带必须严格垂直放置(因此即使长度小于宽度,卷也不能旋转)。另外,卷材可以任意切割,但胶件的接缝也应垂直。此外,每个房间只能使用一种类型的壁纸。并且同一卷纸不能用于不同的房间。也就是说,每个房间的卷都是单独购买的。另外,有些卷可能无法完全使用。

买了公寓后,鲍里斯缺钱,所以他想花最少的钱买壁纸。帮助他。

输入

第一行包含一个正整数 n (1 ≤ n ≤ 500) — 鲍里斯公寓的房间数。

接下来的 n 行中的每一行都包含三个以空格分隔的正整数 - 分别是给定房间中墙壁的长度、宽度和高度(以米为单位)。

下一行包含一个正整数 m (1 ≤ m ≤ 500) — 可用壁纸类型的数量。

以下 m 行中的每一行都包含三个以空格分隔的正整数 - 分别是给定壁纸的长度和宽度(以米为单位)以及一卷的价格。

输入数据中的所有数字不超过500。保证每个房间都可以使用这些类型的壁纸。

输出

打印一个数字 — 卷的最低总成本。

示例

输入 #1

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

输出 #1

640

注意

样本注释:

房间墙壁(周长)的总长度为 20 m。

第一种类型一卷可以切成3条垂直1米宽的条,因此需要7卷这种类型,价格等于700。

第二种的一卷可以切成片,得到5条2米宽的条,我们需要2卷,价格是640。

第三种一卷可以立即纸20米中的19米,但我们不能使用其他类型,我们必须购买第二卷,价格是1000。