该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

西西酱正在准备 CSP 2077 的复赛模拟题，她看中了消消乐这道题目，于是打算改编一下。 首先给定一个长度为 $N$ 的字符串 $S$，仅包含小写字母，再给定 $M$ 种合法操作。 第 $i$ 种操作描述为，若字符串中存在连续 $X_i$ 个字符 $C_i$，则可以将这个子串替换为仅包含 1 个 $C_i$ 的子串。 只要在合法的情况下（存在连续数量的字符满足条件），这些操作可以随意使用，没有顺序要求，也允许重复使用。 而且在执行每次操作前，可以对字符串中的字符进行任意的重排。 西西酱想知道，在最优策略下，最终得到的字符串的最小长度是多少，输出这一长度。

输入格式

第一行两个整数 $N, M$，表示字符串的长度，以及合法的操作种类数。 第二行一个长度为 $N$ 的字符串 $S$，表示初始的字符串。 接下来 $M$ 行，每行一个整数 $X_i$，以及一个字符 $C_i$，表示每种操作。

输出格式

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

输入输出样例

样例 1

输入

4 1
abba
2 a

输出

3

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

样例 2

输入

13 2
aaaaaaaaaaaaa
4 a
12 a

输出

1

样例说明 只需要一直执行第一种操作。

样例3,4,5

见附件 erase.zip

数据范围与提示

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

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