Feeding the Cows

Farmer John has a big square field partitioned into an \((N+1)\times(N+1)\) grid of cells. For \(1 \le i,j \le N\), each cell \((i,j)\) contains a cow and a signpost. Each signpost initially points either to the right (denoted by 'R') or downward (denoted by 'D'). Every cell in the last row (row \(N+1\)) and the last column (column \(N+1\)), except the cell \((N+1,N+1)\), contains a vat of cow feed. The vat at cell \((i,j)\) costs \(c_{i,j}\) to feed each cow.

Every day at dinner time, all cows follow the directions indicated by the signposts in their cells until they reach a vat, at which point they are fed. After feeding, the cows return to their original positions. However, just before dinner on each day, the signpost in one cow cell is flipped (i.e. from right to down or from down to right) and remains in the new direction for subsequent days.

Your task is to calculate the total feeding cost for all cows for each day given \(Q\) days of signpost flips.

Note: The time limit for this problem is 8s, four times the default.

inputFormat

The input begins with a line containing two integers \(N\) and \(Q\) \((1 \le N, Q \le 1500)\).

The next \(N\) lines each contain a string of length \(N\) consisting solely of the characters 'R' and 'D', representing the initial orientation of the signposts in the cow cells (for rows \(1\) to \(N\) and columns \(1\) to \(N\)).

The following line contains \(N\) space-separated integers. These denote the feed costs for the vats in the bottom row (i.e. cell \((N+1,1)\) to \((N+1,N)\)).

The next line contains \(N\) space-separated integers, representing the feed costs for the vats in the right column (i.e. cell \((1,N+1)\) to \((N,N+1)\)).

Finally, \(Q\) lines follow. Each of these lines contains two integers \(i\) and \(j\) \((1 \le i,j \le N)\) indicating that the cow cell at \((i,j)\) has its signpost flipped before dinner on that day.

outputFormat

Output \(Q\) lines. The \(k\)th line should contain one integer: the total cost to feed all cows on day \(k\) after processing that day's signpost flip.

sample

2 1
RD
DR
1 2
3 4
1 1

10