Rune Johan 是一个可爱的小伙子，也是一名聪明的学生，但他一直没能成功地与女性进行富有成效的交谈。当计算机科学系举办舞会并邀请一年级护理系学生时，他非常感激。在那里，他看到了她——他梦寐以求的女人。但像我们大多数人在这种情况下一样，他僵住了，不敢接近她。

在后悔了几天自己的不作为后，Rune Johan 决定弥补。他打听到了她的名字，Celina Middleware，但他不想在制定好周密的计划之前就去接触她。他先找到了她的朋友 Bjørgfrid，并邀请她喝咖啡。交谈了几分钟后，Bjørgfrid 告诉他，她的电脑出了一些问题。Rune Johan 与她达成了一项交易：如果她告诉他关于 Celina 的一切他需要知道的信息，他就帮她修好电脑。

事实证明，Celina 喜欢很多不同类型的男孩，但她仍然相当挑剔。他可以既聪明、有修养又衣着得体，或者拥有一辆摩托车且略显粗鲁。或者他也可以仅仅是富有。Rune Johan 写下了所有信息，回家完成他的计划。他估算了完成每一项标准需要多少周，并试图决定哪种组合花费的时间更少。他认为他可以并行处理所有这些标准。

图 1：Rune Johan 为了征服 Celina Middleware 必须达成的条件。

输入格式

输入的第一行给出了测试用例的数量，最多为 100 个。每个测试用例由两行字符串给出。第一行字符串给出了满足各项标准所需的时间成本，以逗号分隔。每个成本由一个字符串给出，包含标准名称、冒号，以及该标准以周为单位的整数时间成本。名称包含 'a' 到 'z' 的字符，长度为 1 到 20。成本在 0 到 1000 之间（含边界）。最多有 20 个不同的标准。

第二行字符串给出了满足 Middleware 小姐的条件组合。每个组合由符号 '|' 分隔，组合内的各项标准由符号 '&' 分隔。每个场景中有 1 到 10 个组合。每个组合至少包含一个标准，且每个组合中不会重复出现同一个标准。

输出格式

对于每个测试场景，输出一行，表示满足 Celina 的愿望所需的最短时间成本（以周为单位）。

样例

输入 1

3
intelligent:0,cultivated:4,welldressed:2,motorcycleowner:3,rude:8,rich:100
intelligent&cultivated&welldressed|motorcycleowner&rude|rich
ab:13,b:17,cab:21
ab&b|b&cab
a:14,b:13,c:14,d:11
a&b&c|d&a&c|a|b&d

输出 1

4
17
13