You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

西西酱正在准备 CSP 2077 的复赛模拟题，她看中了消消乐这道题目，于是打算改编一下。

首先给定一个长度为 $N$ 的字符串 $S$，仅包含小写字母，再给定 $M$ 种合法操作。

第 $i$ 种操作描述为，若字符串中存在连续 $X_i$ 个字符 $C_i$，则可以将这个子串替换为仅包含 $1$ 个 $C_i$ 的子串。

只要在合法的情况下（存在连续数量的字符满足条件），这些操作可以随意使用，没有顺序要求，也允许重复使用。

而且在执行每次操作前，可以对字符串中的字符进行任意的重排。

西西酱想知道，在最优策略下，最终得到的字符串的最小长度是多少，输出这一长度。

输入格式

第一行两个整数 $N$, $M$，表示字符串的长度，以及合法的操作种类数。

第二行一个长度为 $N$ 的字符串 $S$，表示初始的字符串。

接下来 $M$ 行，每行一个整数 $X_i$，以及一个字符 $C_i$，表示每种操作。

输出格式

输出一行，一个整数，表示最终字符串长度的最小值。

4 1
abba
2 a

3

首先将字符串重排为 "baab"，然后对中间连续的两个 'a' 执行操作，最终得到 "bab"，是最短可能。

13 2
aaaaaaaaaaaaa
4 a
12 a

1

只需要一直执行第一种操作。

【样例 3/4/5】

见附加文件下 erase.zip

数据范围与提示

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le N \le 2500$，$1 \le M \le 50$，字符串 $S$ 中仅包含小写字母。