Johnny 在 Las Figas 度假。他决定去最近开业的 Lohal 赌场。Lohal 为游客提供了一种名为“黑或白”（Black or White）的新游戏。这是一个单人游戏，过程如下：

有 $m$ 个代币排成一行。玩家会被依次提供这些代币。每个代币要么是白色、黑色，要么是钻石。为了获得一个代币，玩家需要购买一张卡片。目前有几种类型的卡片可供选择。

第 $i$ 种类型的卡片上写有两个数字：$w_i$ 和 $b_i$，共有 $c_i$ 张这种卡片。购买第 $i$ 种类型的卡片，玩家必须支付 $w_i + b_i$ 美元，但如果他已经拥有一些代币，则可以获得折扣。

具体来说，如果玩家拥有 $a$ 个白色代币，他可以将卡片上的数字 $w_i$ 减少最多 $a$（但不能使其变为负数）。同样，如果玩家拥有 $b$ 个黑色代币，他可以将数字 $b_i$ 减少最多 $b$（同样不能使其变为负数）。最后，对于每个钻石代币，玩家可以选择将 $w_i$ 或 $b_i$ 中的任意一个减少 1。

例如，如果玩家拥有 2 个白色、1 个黑色和 1 个钻石代币，他可以用 1 美元购买 $w_i = 4, b_i = 0$ 的卡片：2 个白色代币将 $w_i$ 减至 2，使用钻石代币可以将 $w_i$ 进一步减至 1。黑色代币对这张卡片无用，因此现在的成本为 $1 + 0 = 1$。同样的代币组合也可以免费获得 $w_i = 2, b_i = 2$ 的卡片（此时使用钻石代币来减少 $b_i$）。

注意，购买卡片不需要玩家丢弃代币，它们会保留在玩家手中，稍后可以再次用于购买其他卡片。

玩家可以选择获取哪些代币，但为了赢得大奖，他需要获得所有代币。Johnny 想要赢得大奖，所以他决定获得所有代币。请帮助他选择购买哪些卡片来获取代币，使得他赢得大奖所花费的总金额最小。

输入格式

输入文件包含多个测试用例。

每个测试用例以一个整数 $m$ 开始，表示代币数量（$1 \le m \le 300$）。下一行包含 $m$ 个字符，每个字符要么是表示白色代币的 ‘W’，要么是表示黑色代币的 ‘B’，或者是表示钻石代币的 ‘*’。该行按代币提供给玩家的顺序排列。

接下来一行包含 $n$，表示卡片类型的数量（$1 \le n \le 300$）。接下来的 $n$ 行每行包含三个整数：对于每种卡片类型，分别指定 $w_i, b_i$ 和 $c_i$（$0 \le w_i, b_i \le 1000, 1 \le c_i \le 300$）。所有 $c_i$ 的总和至少为 $m$。

最后一个测试用例后跟一行包含 0 的内容，该行不应被处理。

单个输入文件中所有测试用例的 $m$ 之和不超过 300。单个输入文件中所有测试用例的 $n$ 之和不超过 300。

输出格式

对于每个测试用例，输出一个整数：Johnny 赢得大奖所需花费的最小总金额。

样例

样例输入 1

5
WWB*W
3
0 1 1
1 0 1
1 2 3
0

样例输出 1

4

说明

样例中的最优策略如下：