5008 - [COCI 2008-2009 #5] KRUSKA

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

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

如果当前的网格里有一个醒着的巫师，那么 Aladdin 会根据巫师说的话向左或向右转 90 度。

如果向前走会把 Aladdin 带出沙漠，他会转过 180 度。

Aladdin 向前移动了一格，这将花费他一天的时间。

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

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

输入共 m+2 行。

第一行，两个整数 n,k，分别表示沙漠的边长和古老的预言中所说的要改变方向的次数。

第二行，一个整数 m，表示巫师的个数。

随后 m 行，第 i 行两个整数和一个字符串，分别表示巫师所在的横坐标，纵坐标和一个星期内的行动（从星期一开始）。

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

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

【样例 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。