字符串袋子 - 代码源竞赛平台

题目描述

蜗蜗起初有一个空字符串 $S$，面前有按顺序编号的 $N$ 个袋子。第 $i$ 个袋子里装有 $A_i$ 个字符串。

他必须按编号从小到大处理每个袋子。处理一个袋子时，可以花 $1$ 元，从中选择恰好一个字符串接到 $S$ 的末尾；也可以跳过这个袋子。一个袋子不能选择多个字符串，已经处理过的袋子也不能返回。

给定目标字符串 $T$。求最后使 $S=T$ 所需的最少费用；如果无法做到，输出 $-1$。

输入格式

第一行包含目标字符串 $T$。

第二行包含一个整数 $N$，表示袋子数量。

接下来 $N$ 行，第 $i$ 行先给出整数 $A_i$，再给出这个袋子中的 $A_i$ 个字符串 $S_{i,1},S_{i,2},\ldots,S_{i,A_i}$。

输出格式

输出一行一个整数，表示最少费用；无法得到 $T$ 时输出 $-1$。

样例

ab
2
2 a z
1 b

2

abc
2
1 ab
1 c

2

样例解释

样例 1 中，从第一个袋子选 a，从第二个袋子选 b，花费 $2$ 元得到 ab。

样例 2 中，依次选择 ab 和 c，花费 $2$ 元得到 abc。

数据范围

对于 100% 的数据，保证 $1\le |T|\le 100$，$1\le N\le 100$，$1\le A_i\le 10$，$1\le |S_{i,j}|\le 10$；所有字符串均只含小写英文字母。