题目描述

在一家商店中，所有商品的价格都是整数。

例如，一朵花的价格是 2 元，一个花瓶的价格是 5 元。

为了吸引更多的顾客，商店推出了一些特别优惠。

优惠活动将一种或多种商品进行捆绑特价销售，当然售价仍是整数，例如：

• 三朵花的售价为 5 元，而不是 6 元。
• 两个花瓶加一朵花的售价为 10 元，而不是 12 元。

每种优惠方案可以使用无限次。

现在，给定顾客的购买清单以及各种优惠方式，请你计算顾客购买所有所需物品至少需要花多少钱。

举个例子，比如顾客要买三朵花和两个花瓶，那么最低需要花费 14 元，其中两个花瓶加一朵花的价格为 10 元，两朵花的价格为 4 元。

注意，顾客购买各种物品的数量必须恰好与所需数量一致，即使有时多购买某件产品会使得花费更低，也不允许多买。

输入格式

第一行包含整数 $s$，表示优惠方案的数量。

接下来 $s$ 行，每行描述一种优惠方案，首先包含一个整数 $n$，表示这种方案涉及到 $n$ 种商品，接下来包含 $n$ 个数对 $c,k$，表示这种方案需要购买 $k$ 个编号为 $c$ 的商品，最后包含一个整数 $P$ 表示这种优惠方案的商品总价，保证这个优惠价比按原价购买所有涉及商品的花费更低。

接下来一行，包含整数 $b$ 表示顾客要买 $b$ 种商品。

接下来 $b$ 行，每行包含三个整数 $c,k,p$，表示编号为 $c$ 的商品需要购买 $k$ 件，每件的原价为 $p$。

输出格式

输出一个整数，表示购买所有物品所花费的最低价格。

2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5

14

提示

$0≤s≤99,$

$1≤n≤5,$

$1≤k≤5,$

$1≤c≤999,$

$1≤P≤9999,$

$0≤b≤5,$

$1≤p≤999$