题目背景

Aladdin 已经厌倦了宫殿里的生活。他有一份稳定的工作，他的妻子 Jasmine 和孩子们都在路上，生活变得单调。在这一切的驱使下，他决定在安顿下来之前再进行一次冒险。他决定找到 Golden Pear，这是一件极为珍贵的传奇文物，至今无人能找到。

题目描述

Aladdin 正在寻找的沙漠可以被看作是一个 $n×n$ 的网格。行和列从上到下、从左到右编号为 $1$ 到 $n$。沙漠中的网格里一共有 $m$ 个巫师，他们以一种不同寻常的方式帮助 Aladdin 完成任务。

Aladdin 星期一在沙漠的左上角 $(1,1)$ 开始他的任务并面朝右。他的动作包括重复这些步骤：

1. 如果当前的网格里有一个醒着的巫师，那么 Aladdin 会根据巫师说的话向左或向右转 $90$ 度。
2. 如果向前走会把 Aladdin 带出沙漠，他会转过 $180$ 度。
3. Aladdin 向前移动了一格，这将花费他一天的时间。

对于每个巫师，我们都知道他的位置和一周中每一天的活动计划。每个巫师的日程表是一个由七个字母（仅包含L、R 或 S）组成的字符串，每个字符告诉我们巫师在一周中的某一天（从星期一开始）做什么。字母 L 表示 Aladdin 将在这一天被告知向左转，R 表示 Aladdin 将在这一天被告知向右转，而 S 表示巫师那天正在睡觉。

一个古老的预言说，在改变 $k$ 次方向（通过步骤 $1$ 和步骤 $2$）后，Aladdin 会找到 Golden Pear。根据古老的预言，写一个程序来计算冒险将持续多少天。

输入格式

输入共 $m+2$ 行。

第一行，两个整数 $n,k$，分别表示沙漠的边长和古老的预言中所说的要改变方向的次数。
第二行，一个整数 $m$，表示巫师的个数。
随后 $m$ 行，第 $i$ 行两个整数和一个字符串，分别表示巫师所在的横坐标，纵坐标和一个星期内的行动（从星期一开始）。

数据保证不存在在 $(1,1)$ 处的巫师、两个在同一网格的巫师或者在沙漠外的巫师。

输出格式

输出仅一行，一个整数，代表冒险持续的天数。

3 1
0

2

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

4

5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS

10

提示

【样例 1 解释】

对于样例 $1$，Aladdin 移动了两格之后到达沙漠的边缘，随后他转过 $180$ 度，找到了 Golden Pear。所以冒险将持续 $2$ 天。

【样例 2 解释】

对于样例 $2$，Aladdin 在走了两天之后找到了第一个巫师，但是这个巫师此时正在睡觉，所以 Aladdin 继续走了两天，然后他在第 $4$ 天找到了第二个巫师，这个巫师告诉他要向左转，Aladdin 这么做了，然后他来到了沙漠的边缘，转过 $180$ 度，找到了 Golden Pear。所以冒险将持续 $4$ 天。

【数据范围】

对于 $50\%$ 的数据，保证 $k\leqslant 1000$。
对于所有数据，$2\leqslant n\leqslant 200$，$1\leqslant k\leqslant 10^9$，$0\leqslant m\leqslant 10^4$。

【题目来源】

本题来源自 COCI 2008-2009 CONTEST 5 T6 KRUSKA，按照原题数据配置，满分 $130$ 分。

由 Eason_AC 翻译整理提供。