作曲家在乐谱中使用力度记号来表示音符应该演奏得有多响或多轻。

考虑一个 8 级的力度系统：

• ppp：pianississimo（最弱）
• pp：pianissimo（很弱）
• p：piano（弱）
• mp：mezzopiano（中弱）
• mf：mezzoforte（中强）
• f：forte（强）
• ff：fortissimo（很强）
• fff：fortississimo（最强）

当音乐家演奏时，音符演奏的绝对音量有多大或多小实际上并不重要。听众只能听到它们之间的相对差异。假设我们用数字来描述音符的绝对音量，其中较大的数字表示较大的绝对音量。考虑一位音乐家，她演奏的所有音符的音量最高可达 100。当她将音量从 40 变到 70 时，有些听众可能会认为她从 p 变到了 f，而另一些听众则可能认为她从 pp 变到了 mf。

音乐家的诠释在整首乐曲中必须是一致的。也就是说，在两个具有不同力度记号的音符之间，具有更强力度记号的音符必须始终具有严格更大的绝对音量。在两个具有相同力度记号的音符之间，它们的音量可以有所不同（通常是轻微的，但没有严格的要求）。

你刚刚听了一位音乐家演奏了一首包含 $n$ 个音符的乐曲。你对这首乐曲非常熟悉，并且记得作曲家写下的所有力度记号。根据写下的力度记号，这位音乐家的演奏有多一致？你想计算违反力度记号的无序音符对的数量。这样的一对音符在乐谱中不一定是连续的，并且可能相距很远。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 2 \cdot 10^5$），分别表示音符的数量和力度记号变化的次数。

接下来的 $n$ 行，每行包含一个介于 $1$ 和 $10^9$ 之间的整数，表示音乐家演奏的音符的绝对音量。较大的数字表示较大的绝对音量。

接下来的 $m$ 行，每行包含一个从 1 开始的索引 $i$ 和一个力度记号 $d$，表示作曲家写道，从第 $i$ 个音符开始，力度记号应更改为 $d$。每个力度记号是以下 8 个力度记号之一：ppp、pp、p、mp、mf、f、ff、fff。这些力度记号具有不同的索引，并按索引递增的顺序给出。第一个力度记号总是从音符 1 开始。

输出格式

输出一个整数，表示违反力度记号的无序音符对的数量。

样例

输入样例 1

8 6
10
15
20
30
19
20
35
40
1 p
3 f
4 ff
5 p
7 f
8 ff

输出样例 1

2

说明

第一对违反力度记号的音符是音符 3（音量为 20，力度记号为 f）和音符 6（音量为 20，力度记号为 p）。

第二对违反力度记号的音符是音符 4（音量为 30，力度记号为 ff）和音符 7（音量为 35，力度记号为 f）。

输入样例 2

12 5
5
10
9
20
30
40
90
90
11
10
4
3
1 p
4 f
7 ff
9 p
11 ppp

输出样例 2

0