题目描述

奥尔菲斯长大后成为了小说家。他写了一部小说，这里用非空字符串 $t$ 来表示。

小说有很多种解读方式，更具体地，奥尔菲斯认为小说可以通过分成若干个片段来解读。当然，随意切分出来的片段往往是没有意义的。奥尔菲斯给出了 $n$ 个有意义的片段，这里用非空字符串 $s_1,s_2,\dots,s_n$ 来表示。奥尔菲斯认为每个片段有相应的价值，这里用正整数 $c_1,c_2,\dots,c_n$ 来表示。

一种解读方式是有价值的当且仅当切分出来的每个片段都是有意义的，有价值的解读方式的价值是各个片段的价值之和。奥尔菲斯想知道小说是否有有价值的解读方式，如果有，他还想知道价值最大是多少。

形式化地，设想一个空字符串 $str$。你可以执行以下操作任意次数：

• 选择一个索引 $i\in\{1,2,\dots,n\}$；
• 将 $s_i$ 追加到 $str$ 末尾；
• 该操作的价值是 $c_i$。

计算是否有可能使 $str$ 等于 $t$，如果不可能，输出 $-1$；如果可能，输出各次操作价值之和的最大值。

输入格式

本题的测试点包含有多组测试数据。

输入的第一行包含一个正整数 $q$，分别表示测试数据组数。

接下来，对于每组测试数据：

• 输入的第一行包含一个正整数 $n$。
• 输入的第二行包含 $n$ 个正整数 $c_1,c_2,\dots,c_n$。
• 接下来的 $n+1$ 行每行包含一个字符串，依次为 $t,s_1,s_2,\dots,s_n$。

输出格式

对于每组测试数据输出一行一个整数，表示答案。如果不存在有价值的解读方式，请输出 $-1$，否则输出解读方式的最大价值。