问题描述

Nathan O. Davis正在经营一家公司。他的公司拥有一个拥有很多用户的网络服务。所以他的办公室里到处都是服务器、路由器和凌乱的局域网电缆。

他现在非常困惑于这些凌乱的电缆，因为它们会导致各种问题。例如，公司工作人员经常会绊倒在电缆上。如果电缆断开没有损坏就很幸运了。如果电缆连接，计算机可能会倒下并损坏。他即将引入一台新计算机和一根新电缆。他希望最大限度地减少员工踩踏新电缆的次数。

他的办公室布局是一个二维网格，大小为 $H \times W$ 个单元格。新电缆应该沿着单元格的边缠绕。电缆的每一端都位于一个单元格的角落。网格用从零开始的坐标表示，左上角为 (0, 0)。

每个员工从某个单元格内开始工作，每天按照固定的重复模式沿着网格在办公室中行走。一个行走模式由一个包含四个字符 U、D、L 和 R 的字符串描述。U 表示向上移动，D 表示向下移动，R 表示向右移动，L 表示向左移动。例如，UULLDDRR 表示依次向上、上、左、左、下、下、右、右移动。员工重复此模式 $T$ 次。请注意，如果员工将要穿过墙壁跑出网格，则员工会留在原单元格。

您已经知道所有员工的行走模式和新电缆两端的位置。您的任务是找到新电缆的最佳放置位置，以最小化员工踩踏电缆的总次数。

输入

输入的第一行包含三个整数，表示办公室的尺寸 $W$、$H$ ($1 \leq W, H \leq 500$) 和员工的数量 $N$ ($1 \leq N \leq 1000$)。接下来一行包含两个 $x-y$ 对 ($0 \leq x \leq W$，$0 \leq y \leq H$)，表示要连接的局域网电缆的两个端点的位置。这些值表示电缆插入其左上角的单元格的坐标。特别地，$x = W$ 表示最右侧单元格的右边缘，$y = H$ 表示最下方单元格的底边。

接下来的几行描述了员工的初始位置和他们的移动模式。第一行包括一个 $x$-$y$ 对 ($0 \leq x \lt W$，$0 \leq y \lt H$)，表示员工初始单元格的坐标。接下来一行包含一个整数 $T$ ($1 \leq T \leq 100$) 和一个由 U、D、L 和 R 组成的字符串，其含义如上所述。模式字符串的长度大于等于 $1$，不超过 $1,000$。这两行重复出现 $N$ 次。

输出

在一行中输出员工踩踏电缆的最小次数。

示例输入 1

3 3 1
1 1 3 3
0 0
1 RRDDLLUU

示例输出 1

1

示例输入 2

3 3 1
0 0 3 3
0 0
1 RRDDLLUU

示例输出 2

0

示例输入 3

3 3 1
1 1 3 3
0 0
10 RRDDLLUU

示例输出 3

10

示例输入 4

3 3 4
1 1 3 3
0 0
10 R
2 0
10 D
2 2
10 L
0 2
10 U

示例输出 4

1

出处

夏令营 2013