题目 C：DNA 序列合成 (DNA)

题目描述

DNA 链可以表示为由四种脱氧核苷酸（A、T、C、G）组成的序列。DNA 链的长度是指序列中核苷酸的数量。例如，ATCATC 的长度为 6，AAA 的长度为 3。

我们可以通过拼接两个或多个 DNA 片段来构造一条新的 DNA 链。给定一条长度为 $N$ 的目标 DNA 链和 $M$ 个可选的 DNA 片段，你需要计算构造出目标链所需的最少片段数量。每个片段可以使用任意次数（包括 0 次）。

输入格式

• 第一行：两个整数 $N$ ($1 \le N \le 5000$) 和 $M$ ($1 \le M \le 100000$)。
• 第二行：长度为 $N$ 的目标 DNA 字符串。
• 接下来共 $2M$ 行：每两行描述一个片段。第一行为片段长度 $L_i$，第二行为该片段的 DNA 序列。
• 数据保证：$1 \le L_i < N$，所有片段长度之和不超过 $1,000,000$。

输出格式

• 输出一个整数，表示构造目标链所需的最少片段数。如果无法构造，则输出 -1。

非常抱歉！由于之前的回复较长，可能在排版时漏掉了最直观的样例部分。这里为你补全 Problem C (DNA) 的完整样例说明，并附带逻辑解析，帮助你更好地理解。

样例输入与输出 (Problem C: DNA)

样例 1

输入：

6 3
ATCATC
2
AT
2
TC
2
CA

输出：

3

解释： 目标是 ATCATC。我们可以按以下顺序拼接：

1. 使用 AT (长度2) -> 剩余 CATC
2. 使用 CA (长度2) -> 剩余 TC
3. 使用 TC (长度2) -> 完成 总共使用了 3 个片段。

样例 2

输入：

6 4
ATCATC
2
AT
2
TC
2
CA
3
ATC

输出：

2

解释： 相比样例1，增加了一个长度为 3 的片段 ATC。

1. 使用 ATC (前3位)
2. 使用 ATC (后3位) 总共只需 2 个片段。这比样例1的方案更优，所以输出 2。

样例 3

输入：

3 2
AAA
1
T
2
AA

输出：

-1

解释： 目标是 AAA。

• 片段 1 是 T，目标链里没有 T。
• 片段 2 是 AA，只能盖住前两位，剩下一个 A 无法由现有片段组成。 因此输出 -1。