P9014 [USACO23JAN] Following Directions S

**注：本题时限为 8s，是默认时限的四倍。** Farmer John 有一个正方形的草地，草地被划分为了 $(N + 1) \times (N + 1)(1 \leq N \leq 1500)$ 的格子。设 $(i, j)$ 为从上到下、从左到右第 $i$ 行，第 $j$ 列的格子。每个满足 $1 \leq i, j \leq n$ 的格子 $(i, j)$ 之中都住着一头牛，而且每个这样的格子上都有一个路标指向右或下。除此之外，所有满足 $i = N + 1$ 或 $j = N + 1$ 的格子，除了 $(N + 1, N + 1)$ 都会有一个饲料桶。牛在每个饲料桶进食需要的价格不同；位置 $(i, j)$ 上的桶喂饱一只牛需要价格 $c_{i, j}(1 \leq c_{i, j} \leq 500)$。 每天晚饭时间，Farmer John 摇响晚餐铃时，所有牛都沿着路标的指向前进，直到它们遇到了饲料桶，之后它们会在它们自己遇到的饲料桶那里进食。第二天，所有牛又会回到自己原来的位置。 为了维持预算，Farmer John 想要知道每天喂食需要的价钱。然而，每天晚饭之前，总会有一头牛 $(i, j)$ 翻转它那里的路标（原来向下则变成向右，反之亦然）。被翻转的路标指向将在后面的日子里保持不变，除非它又被进行了翻转。 给出每天被翻转的路标的坐标，请输出每天喂食需要的价格（总共有 $Q$ 天，$1 \leq Q \leq 1500$）。

第一行为 $N(1 \leq N \leq 1500)$ 接下来的 $N + 1$ 行从上到下输入初始的路标朝向和每个饲料桶的价格 $c_{i, j}$。前 $N$ 行每行包含一个长度为 $N$ 的字符串，其中每个字符只能是 `R` 或 `D`（`R` 表示向右，`D` 表示向下），之后是一个数，表示价格 $c_{i, N + 1}$，第 $(N + 1)$ 行包含 $N$ 个数，依次表示价格 $c_{N + 1, j}$。 接下来的一行为 $Q(1 \leq Q \leq 1500)$。 之后的 $Q$ 行，每行有两个整数 $i$ 和 $j(1 \leq i, j \leq N$，表示每天被翻转的路标的坐标。

共 $Q + 1$ 行：第一行是初始的总价格，之后 $Q$ 行依次是每次被翻转后的总价格。

### 样例 1 解释 在第一次翻转之前，喂养在位置 $(1, 1)$ 和 $(1, 2)$ 的牛需要的价格都为 $1$，喂养在 $(2, 1)$ 的牛需要的价格为 $100$，喂养在 $(2, 2)$ 的牛需要的价格为 $500$。总价格为 $602$。第一次翻转后，在 $(1, 1)$ 处的路标由 `R` 变为 `D`，此时在位置 $(1, 1)$ 的牛喂养的价格变为 $100$（其它牛的价格没有变化），所以总价为 $701$。第二次和第三次翻转都在来回翻转同一个路标。第四次翻转后，在位置 $(1, 1)$ 和位置 $(2, 1)$ 的牛喂养的价格变为 $500$，总价变为 $1501$。 - 测试点 $2 - 4$ 中：$1 \leq N, Q \leq 50$。 - 测试点 $5 - 7$ 中：$1 \leq N, Q \leq 250$。 - 测试点 $2 - 10$ 中：每个路标初始朝向以及被翻转的路标为随机生成。 - 测试点 $11 - 15$ 中：无特殊条件。