题目描述

给定一组代码词和一个文本。假设文本中包含由这些代码词组成的隐藏信息，这些代码词以特定（可能具有歧义）的方式嵌入在文本中。

代码词和文本仅由英文字母的大小写组成，且区分大小写。代码词的长度按常规方式定义，例如代码词ALL的长度为$3$。

代码词的字母不必连续出现在文本中。例如，代码词ALL可能出现在形如AuLvL的子序列中，其中$u$和$v$表示任意（可能为空）的字母序列。我们称AuLvL是ALL的一个覆盖序列。
一般地，代码词的覆盖序列定义为：

• 该子序列的首字母和末字母必须与代码词的首字母和末字母相同；
• 可以通过删除该子序列中的某些字母（可能不删除）得到代码词。

覆盖序列由其起始位置（首字母在文本中的位置）和结束位置（末字母在文本中的位置）标识（文本的首字母位置为$1$）。
如果两个覆盖序列$c_1$和$c_2$满足$c_1$的起始位置$>$ $c_2$的结束位置，或反之，则称它们不重叠；否则称它们重叠。

任务要求

从文本中提取隐藏信息，需构造一个解，该解为若干项的集合，每项包含一个代码词及其覆盖序列，并满足以下条件：

1. 所有覆盖序列之间互不重叠；
2. 每个覆盖序列的长度不超过$1000$；
3. 所有代码词的长度之和最大。

输入格式

• 第一行：代码词数量$N$（$1 \leq N \leq 100$）；
• 接下来的$N$行：每行一个代码词（长度不超过$100$）；
• 最后一行：文本（长度不超过$1,000,000$）。

输出格式

• 一行，输出解中所有代码词的长度之和的最大值。

示例输入

4
RuN
RaBbit
HoBbit
StoP
StXRuYNvRuHoaBbvizXztNwRRuuNNP

示例输出

12

补充说明

• 右极小覆盖序列：若覆盖序列$c$的任意真前缀均不能作为代码词$w$的覆盖序列，则称$c$是$w$的右极小覆盖序列。
• 题目保证：
  1. 文本中每个位置涉及的右极小覆盖序列不超过$2500$个；
  2. 右极小覆盖序列总数不超过$10,000$个。

题目来源

IOI 1999