You have been hired as a Temporary Part-Time Assistant Manager of the Executive Municipal Internet Service Provider Administration!

Your job is to set up cell towers to provide internet to homes in The City.

The City can be visualized as a very large rectangular grid. The rows are numbered starting from $$$1$$$, from south to north. The columns are numbered starting from $$$1$$$, from west to east. There are also $$$n$$$ houses on this grid, denoted by $$$(r, c)$$$, where $$$r$$$ is the number of the row the house is in, and $$$c$$$ is the number of the column the house is in.

You are trying to install cell towers for the houses. However, the cell towers have a peculiar set of rules.

A cell tower can only provide signal to a right isosceles triangle that extends south and east from it. More formally, a cell tower at $$$(r, c)$$$ covers all houses $$$(r', c')$$$, such that $$$c \leq c'$$$, and $$$r' + c' \leq r + c$$$.

If a cell tower is set at $$$(3, 1)$$$, it can only provide signal to houses at $$$(3, 1), (2, 1), (1, 1), (2, 2), (1, 2), (1, 3)$$$. Here is a diagram of the range of a cell tower at $$$(3, 1)$$$:

Because the terrain gets rougher the further north you go, the cost of a cell tower is equal to the number of the row it is installed. For instance, installing a cell tower at $$$(3, 1)$$$ has a cost of $$$3$$$.

A cell tower may be installed on top of houses, and it will still provide coverage as usual (despite protests from homeowners).

The City is a bit indecisive about how many cell towers they would like to install. Thus, for every $$$i$$$ from $$$1$$$ to $$$n$$$, find the minimum cost to cover all houses with at most $$$i$$$ cell towers.