题目描述

乐乐正在玩一个特别的消消乐游戏哦！在游戏中，屏幕上会显示一行由很多小写字母组成的字符串s，这个字符串有n个字母。然后，游戏会有x个关卡，每个关卡都有它的特别要求。

在每个关卡开始时，乐乐会看到两个数字a和b（a<=b），这两个数字告诉乐乐，字符串s中从第a个字母到第b个字母会亮起来。亮起来的这些字母就是乐乐可以点击的字母。

如果乐乐按照顺序点击了“ok”这两个字母，或者“good”这四个字母，那么这些被点击的字母就会立刻变暗，而且乐乐就能得到1分,每关该操作均能执行多次。如果乐乐在这一关卡中找不到可以组成“ok”或者“good”的亮起字母了，那么这一关就结束了，游戏会进入下一关。

如果乐乐参加了所有的x关卡，他最多能拿到多少分呢？

输入格式

第一行，两个正整数n，x，分别表示字符串的长度和关卡数量。

第二行，一个字符串s。

接下来x行，每行两个正整数a,b(1<=a<=b<=n),表示该关开始时，字符串s中从第a个字母到第b个字母会亮起来。

输出格式

一个整数，为乐乐最多能拿到的分数。

12 2
‌keenkgoodjob
1 8
6 12

3

样例解释

第1关，亮起的字符串为‌keenkgoo，可以先后点击第7个字母和第1个字母，凑成“ok”,得1分，再点击第8个字母和第5个字母，再得1分，此时无法再得分。第二关亮起的字母为goodjob，可以点击“good”，得1分，共得3分。

数据范围

60%数据，n<=1000，x<=10

100%数据，1<=n,x<=1000000