SP9121 GCPC11E - Magical Crafting

你很喜欢玩《我的世界》，于是想为它添加一个魔石模组。 你添加了一些关于魔石的合成配方：一块魔石 $m_1$ 可以和一些钻石合成两块魔石 $m_2$，$m_3$。这些魔石的用途是照明，在这里，魔石用大写字母表示，而一个魔石对应转换而成的光源是小写字母。例如，魔石 'A' 所转换的光源是 'a' ，转换的代价是一个钻石。如果你不把魔石合成成别的魔石，那么它就会转换成灯光。如果你用魔石 $m_1$ 合成了魔石 $m_2$、$m_3$，那么（如果都不继续合成的话）$m_2$ 会比 $m_3$ 更早亮起。 钻石太稀有了，可是你又想用魔石看到 $L$ 个完整的灯光序列，你只解锁了 $R$ 个魔石合成配方，你想知道最少要花多少钻石才能看到想要的灯光序列。

第一行一个测试样例个数 $C$。 后面 $C$ 组数据，每组第一行是 $R$，$L$。 之后的 $R$ 行有三个大写字母，一个数字，分别代表 $m_1$，$m_2$，$m_3$ 和此合成配方花费的钻石数。 再然后的 $L$ 行每行有一个数字和一个字符串，分别代表灯光序列中灯光的个数和灯光序列，保证灯光序列只包含小写字母。

输出共 $C$ 组，每组第一行是 **CASE #每组测试数据的编号** ，后面对应的 $L$ 行每行为 **POSSIBLE WITH X DIAMONDS** ， X 为需要的灯光序列要多少钻石，如果需要的灯光序列无法实现，那么那一行输出 **IMPOSSIBLE** 。