P7683 [COCI 2008/2009 #5] KRUSKA

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)$ 处的巫师、两个在同一网格的巫师或者在沙漠外的巫师。

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

**【样例 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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST 5](https://hsin.hr/coci/archive/2008_2009/contest5_tasks.pdf) T6 KRUSKA_**，按照原题数据配置，满分 $130$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。