T139030 「MCOI-01」Seed 种子

WAPER 爱玩 Minecraft 生存！

众所周知，在开启一个新的 Minecraft 存档时，可以输入一个种子来决定生成的地图。 为了方便，定义种子可以被形容为一个 **任意长度** 的 **只包含小写字母和下划线（注意这个下划线）** 的字符串 $S$。 总所周知，有时候生成的地图开局运气特别好，一挖就能挖到钻石，而有时却出生在一个一棵树都没有的小岛上。 经过 WAPER 长期不断的实验，发现有 $n$ 个 **只包含小写字母的（没有下划线）** 字符串（第 $i$ 个字符串为 $T_i$），若 $S$ 包含 $T_i$ 长度为 $j$ 的前缀，则可以获得 $V_{i,j}$ 的运气。 现在 WAPER 想找到一个种子 $S$，使得他获得的运气值最大，请您帮他求出最大的运气值。 **若 $S$ 中有多个 $T_i$ 长度为 $j$ 的前缀，$V_{i,j}$ 只算一次，$S$ 可以为空串。**

**本题有多组数据。** 第一行一个整数 $t$ 代表数据组数。 对于每组数据： 第一行一个整数 $n$ 代表字符串数。 接下来 $n$ 行每行一个只包含小写字母的字符串 $T_i$。 接下来 $n$ 行第 $i$ 行 $|T_i|$ 个整数，第 $j$ 个整数表示 $V_{i,j}$。

对于每组数据： 一行一个整数代表 WAPER 能得到的最大运气值。

#### 样例说明 对于样例 $1$ 的第 $1$ 组数据，$S=$ `abc` 时是一种可行的最优解。 对于样例 $1$ 的第 $2$ 组数据，$S=$ `aba_ab` 时是一种可行的最优解。 对于样例 $1$ 的第 $3$ 组数据，$S$ 为空串时是一种可行的最优解。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：满足性质 B 和性质 C。 - Subtask 2（20 pts）：满足性质 A 和性质 B。 - Subtask 3（35 pts）：满足性质 B。 - Subtask 4 （40 pts）：无特殊性质。 对于 $100\%$ 的数据，$1 \le n,\sum|T_i| \le 500$，$-2000 \le V_{i,j} \le 2000$，$1 \le t \le 5$。 - 性质 A：$V_{i,j}$ 为正数。 - 性质 B：$1 \le n,\sum|T_i| \le 200$。 - 性质 C：所有 $T_i$ 均相等。 除了 Subtask 4，其他三个 Subtask 的数据均为随机。 再次强调，$S$ 可以有下划线，$T_i$ 不会有下划线。 #### 说明 Minecraft OI Round 1 C - Idea：WAPER420 - Solution/Std：WAPER420 - Data：一只书虫仔&\_TNT\_&WAPER420 - Tester：limaopipi2022