时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在一个包含 \(N+1\) 行 \(N+1\) 列的网格上，从上到下的每一行依次编号为 \(1..N+1\)，从左到右的每一列也依次编号为 \(1..N+1\)。用坐标 \((x,y)\) 来表示 \(x\) 行 \(y\) 列的格子。

　　在这个网格中，除第 \(N+1\) 行和第 \(N+1\) 列外，其余的每个格子都有一只蚂蚁，且每个这样的格子上还有一个路标指向右或下。在第 \(N+1\) 行和第 \(N+1\) 列的格子中，除 \((N+1,N+1)\) 的格子外，其他格子里都会有一些糖果，不同格子的糖果的花费可能不同。

　　每天所有蚂蚁都会吃一次糖，到了吃糖时间，蚂蚁们都会沿着路标所指向的方向前进走到最后一行或左后一列有糖果的格子里，然后它们会在遇到糖果格子那里吃糖。吃完后，所有蚂蚁又会回到自己原来的位置。这样的事情每天都会重复一次。

　　为了节约预算，蚁王想要知道每天吃糖需要的花费。然而，在每天吃糖之前，总会有一头蚂蚁翻转它那里的路标（原来向下则变成向右，反之亦然）。被翻转的路标指向将在后面的日子里保持不变，除非它又被翻转了。

　　现在给出每天被翻转路标的坐标，请输出每天吃糖需要的花费。

【输入格式】

　　第一行为 \(N(1≤N≤1500)\)。
　　第 2 到第 \(N+1\) 行从上到下输入初始的路标朝向和每行最后一列格子里糖果的花费。每行包含一个长度为N的字符串，其中每个字符只能是R或D（R表示向右，D表示向下）。该行的最后一个数，表示糖果花费 \(c_i(1≤c_i≤500)\)。
　　第 \(N+2\) 行包含 \(N\) 个数，依次表示第 \(N+1\) 行的前 \(N\) 个格子里糖果的花费 \(p_j(1≤p_j≤500)\)。
　　第 \(N+3\) 行行为整数 \(Q(1≤Q≤1500)\)，表示有 \(Q\) 天时间。
　　之后的 \(Q\) 行，每行有两个整数 \(x\) 和 \(y(1≤x,y≤N)\)，表示每天被翻转的路标的坐标是 \(x\) 行 \(y\) 列。

【输出格式】

　　共 \(Q+1\) 行，第一行是初始的总花费，之后 \(Q\) 行依次是每次被翻转后的总花费。

【输入输出样例1】

　Input

2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1

　Output

602
701
602
701
1501

【样例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】

　Input

8
DDRDRRRD 20
DRDDRDRR 50
RRDRRDDR 30
RDDRDDRR 100
DDRRRDDD 10
RDRDRDRD 70
RRRDRRRD 30
RDRDRDRR 60
30 20 10 90 50 60 40 80
7
2 3
1 8
3 5
8 4
4 4
2 7
7 8

　Output

4210
4210
4090
4090
3670
3670
3720
2700

【测试点性质】

　　- 测试点 \(1 - 4\) 中：\(1 \leq N, Q \leq 50\)。
　　- 测试点 \(5 - 7\) 中：\(1 \leq N, Q \leq 250\)。
　　- 测试点 \(2 - 10\) 中：每个路标初始朝向以及被翻转的路标为随机生成。
　　- 测试点 \(11 - 15\) 中：无特殊条件。

【来源】

　　Mr.he