Gathering clams

The seaside city of Jeongol is divided into districts that form a square grid. One household lives in each district, and the fish market is in the top left district. A household lives in that district as well.

A household on its way to the fish market uses only these two moves.

1. move to the district directly above
2. move to the district directly to the left

Every household walks to the fish market each day, picks up clams in the districts it passes through, and sells them at the market. A household also picks up clams in its own district and in the district with the fish market.

To protect nature, each district sets the largest number of clams that one household passing through it may pick up. There are enough clams that every household passing through picks up that many.

For example, suppose the grid has 3 rows and 3 columns and the limit of each district is the left table below.

The largest number of clams each household can sell at the market in one day is the right table. A household starting in the bottom right district moves up twice and left twice and picks up $8+6+7+2+3=26$ clams, which is the maximum for that district. Adding the maxima of all nine districts gives $3+5+12+7+9+18+12+15+26=107$.

City officials survey the clams regularly and revise the limit of a district. A sudden change is risky, so one revision changes a limit by $+1$ or by $-1$. Limits of districts that are not revised stay the same. For example, if the $2$ in row 1, column 2 of the left table becomes $3$, the two tables change as follows.

You are given the initial limit of every cell and a list of revisions. For the initial state and for the state right after each revision, compute the sum over all districts of the largest number of clams a household can sell in one day.

The first line has an integer $N$, the number of rows and the number of columns of the grid ($2 \le N \le 1500$).

Each of the next $N$ lines holds one row of limits, starting from the top row. Within a line the values are listed from the leftmost column, and every value is between $0$ and $1000$.

Each of the next $N$ lines holds one revision. A revision starts with the letter U or D, then a single space, then the row number and the column number. U raises the limit of that cell by $1$, and D lowers it by $1$. A revision never makes a limit negative. Each revision applies to the grid with all earlier revisions already applied.

Print the sum over all districts of the largest number of clams sellable in one day for the initial grid. Then apply the revisions in order and print the same sum after each one, one value per line. The output has exactly $N+1$ lines.