5008 - [COCI 2008-2009 #5] KRUSKA

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

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

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

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

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

对于每个巫师,我们都知道他的位置和一周中每一天的活动计划。每个巫师的日程表是一个由七个字母(仅包含 LRS)组成的字符串,每个字符告诉我们巫师在一周中的某一天(从星期一开始)做什么。字母 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 2001\leqslant k\leqslant 10^90\leqslant m\leqslant 10^4

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题