题目描述

有一个 $n\times m$ 的棋盘，行编号为 $0,1,\ldots,n-1$，列编号为 $0,1,\ldots,m-1$。每个格子要么为空，要么恰好有一个棋子。

一次操作会指定一个当前格子 $(x,y)$ 和一个方向：上、下、左、右。只有在以下条件同时满足时，这次操作才合法：

• $(x,y)$ 中有棋子；
• 指定方向上存在相邻格子；
• 该相邻格子为空。

随后将棋子从 $(x,y)$ 移动到该相邻格子。

现在给定一段长度为 $q$ 的操作记录。第 $i$ 次操作给出起点 $(x_i,y_i)$ 和方向 $d_i$，其中 U、D、L、R 分别表示上、下、左、右。

如果存在某一种初始棋盘状态，使得可以按照给定顺序依次完成所有操作，则称这段操作记录是合法的。

你可以从记录中删除若干次操作，但剩余操作之间的相对顺序不能改变。请计算至少需要删除多少次操作，才能使剩下的记录合法。

输入格式

第一行三个整数 $n,m,q$。

接下来 $q$ 行，第 $i$ 行两个整数 $x_i,y_i$。

最后一行一个长度为 $q$ 的字符串 $d$，其第 $i$ 个字符表示第 $i$ 次操作的方向。

输出格式

输出一个整数，表示最少需要删除的操作数。

样例输入

2 2 4
0 0
1 0
1 1
0 1
DRUL

样例输出

0

数据范围

• $2\le n,m\le 50$；
• $1\le q\le 1000$；
• $0\le x_i<n$；
• $0\le y_i<m$；
• $d_i\in\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$。