### 题目描述 依依和妮妮正在玩一个有趣的迷宫游戏。这个游戏在一个 $n \times m$ 的网格迷宫中进行，左上角的格子是起点，右下角的格子是终点。每次，依依和妮妮可以选择向右或向下移动一步。然而，站在格子上都需要一定的成本，成本是格子上的整数值，站在 $(x, y)$ 上时，需要消耗成本 $w_{ij}$。 为了增加游戏的难度，依依和妮妮在 $k$ 个格子上设置了障碍物，每个障碍物都有一个额外的成本。如果他们选择经过障碍物，他们需要支付额外的成本。 另外，她们在 $p$ 个格子上设置了陷阱，当她们到达这些位置时，她们将被迫向下或向右移动两步，而不是一步。每个陷阱的移动方向是确定的，移动两步的总成本包括陷阱格子本身的成本和他们被迫移动的两步的成本。 你的任务是帮助依依和妮妮计算出他们在最优策略下可能需要支付的最小总成本。 ### 输入格式 第一行包含三个整数 $n$，$m$，$k$ 和 $p$，分别表示迷宫的长、宽，障碍物的数量和陷阱的数量。 接下来的 $n$ 行，每行 $m$ 个整数，描述了迷宫的初始移动成本。 接下来的 $k$ 行，每行三个整数 $x_i$，$y_i$ 和 $c_i$，表示一个障碍物的位置和额外的移动成本。 接下来的 $p$ 行，每行三个元素，第一个和第二个元素是整数 $x_i$ 和 $y_i$，表示陷阱的位置，第三个元素是一个字符，如果是 `D`，表示陷阱的移动方向是向下，如果是 `R`，表示陷阱的移动方向是向右。 ### 输出格式 输出一个整数，表示依依和妮妮在最优策略下可能需要支付的最小总成本。 ### 样例输入 ``` 3 1 1 1 2 3 4 5 6 7 8 9 2 2 1 3 1 R ``` ### 样例输出 ``` 21 ``` ### 说明 最优策略是先向右移动两步，然后向下移动两步，需要支付的总成本是 $1+2+3+6+9=21$。 ### 数据范围 对于 $100$% 的数据，保证 $1 \leq n, m \leq 1000$，$1 \leq k, p \leq \min(n \times m, 1000)$，$1 \leq w_{ij}, c_i \leq 1000$。 数据保证一个位置最多只有一个障碍物且最多只有一个陷阱，但可能同时有障碍物和陷阱。