CF139B Wallpaper

在买下自己的公寓后，Boris 决定给每个房间的墙壁贴上壁纸。Boris 的公寓有 $n$ 个房间，每个房间都是一个长方体。对于每个房间，已知其长度、宽度和墙高（单位为米，不同房间的尺寸，包括高度，可能不同）。 Boris 选择了 $m$ 种壁纸来装饰房间的墙壁（但不一定要用到所有种类）。每种壁纸以固定长度和宽度的卷出售（长度指的是展开后的长度）。此外，每种壁纸还给出了每卷的价格。 每种壁纸的花纹沿着卷的长度方向排列。粘贴时，壁纸条必须严格竖直放置（即使壁纸卷的长度小于宽度，也不能旋转使用）。此外，一卷壁纸可以任意裁剪，但拼接处也必须竖直。每个房间只能使用一种类型的壁纸。同一卷壁纸不能用于不同房间。也就是说，每个房间需要单独购买壁纸卷，且部分壁纸卷可以不完全用完。 买完公寓后，Boris 手头拮据，所以他希望用最少的钱买壁纸。请你帮他计算最小总花费。

第一行包含一个正整数 $n$（$1 \leq n \leq 500$），表示 Boris 公寓中的房间数。 接下来的 $n$ 行，每行包含三个用空格分隔的正整数，分别表示该房间的长度、宽度和墙高（单位为米）。 接下来一行包含一个正整数 $m$（$1 \leq m \leq 500$），表示可选的壁纸种类数。 接下来的 $m$ 行，每行包含三个用空格分隔的正整数，分别表示该种壁纸的长度、宽度（单位为米）和每卷的价格。 输入数据中的所有数字均不超过 $500$。保证每个房间都可以用这些壁纸类型中的某一种全部贴完。

输出一个整数，表示购买壁纸卷所需的最小总费用。

样例说明： 房间的墙壁总长度（即周长）为 $20$ 米。 第一种壁纸每卷可以裁剪成 $3$ 条竖直、宽度为 $1$ 米的壁纸条，因此需要 $7$ 卷，总价为 $700$。 第二种壁纸每卷可以裁剪成 $5$ 条竖直、宽度为 $2$ 米的壁纸条，因此需要 $2$ 卷，总价为 $640$。 第三种壁纸每卷可以一次性贴满 $20$ 米中的 $19$ 米，但由于不能混用其他类型，还需再买一卷，总价为 $1000$。 由 ChatGPT 4.1 翻译