样例下载

题目描述

某文具店有若干种文具正在进行捆绑销售。

所谓捆绑销售是指，如果顾客购买特定的组合，则会有优惠，使得比原价购买的价格更低。

例如：假设一支铅笔原价是 1 元钱，一块橡皮原价是 2 元钱。

假如现在有以下两种捆绑销售方式：

• 1、同时购买 2 支铅笔的捆绑销售价为 1 元。
• 2、同时购买 4 支铅笔和 2 块橡皮的捆绑销售价为 6 元。

如果要恰好购买 5 支铅笔和 2 块橡皮，则最少需要花费 7 元（使用第二种捆绑方式购买 4 支铅笔和 2 块橡皮花费 6 元，再原价购买 1 只铅笔花费 1 元）。

虽然同时使用两种捆绑方式，花费也为 7 元，还多得 1 支铅笔，看起来更划算一些，但这不是恰好购买。

现在小明要去购买一批文具，文具有若干种，编号为 1, 2, 3, ……，每一种需要购买一定的数量。

问：如何搭配购买可以使他花费的钱数最少？你只需要输出他的最小花费。

注：对于每种文具，小明必须恰好购买指定数量，不能多买，也不能少买。

输入格式

第 1 行：捆绑销售方式的数目 T。（$0 ≤ T ≤ 100$）

接下来 T 行，每一行包含若干个整数，代表一种捆绑销售方式，格式如下：

• 第一个整数 N，表示当前这种捆绑销售方式中包含的文具种类数；接着是 N 对整数 $s_i$ 和 $k_i$，表示有 $k_i$ 个第 $s_i$ 种文具被捆绑到这种销售方式；最后一个整数 P 表示这种方式的捆绑销售价。数据保证捆绑销售价一定低于原价购买总价钱。（$1 ≤ N ≤ 5, 1 ≤ k_i ≤ 5, 1 ≤ s_i ≤ 1000, 1 ≤ P ≤ 10000$）

再接下来一行：一个整数 M，表示需要购买的文具种数。（$0 ≤ M ≤ 5$）

接下来 M 行：每行三个整数 $s_i, k_i, p_i$，表示需要购买 $k_i$ 个第 $s_i$ 种文具，该文具的原价（单价）为 $p_i$（$1 ≤ s_i ≤ 1000, 1 ≤ k_i ≤ 5, 1 ≤ p_i ≤ 1000$）。

输出格式

一个整数，表示恰好购买所需文具的最小花费。

样例输入

2
1 8 2 1
2 8 4 9 2 6
2
8 5 1
9 2 2

样例输出

7

样例解释

假设铅笔的编号为 8，橡皮的编号为 9，则输入样例即是题目描述中的例子。