Key insight I missed!!!

If sum of any h by w rectangle is negative, how come the sum as a whole is positve?

Consider the 1 row case, it becomes clear that if such thing can happen only if W % w != 0. Otherwise, the sum of the whole row can be broken down the the sum of W/w non-intersecting subrows => but the sum of all these negative numbers can not be postivie.

By extension, in H by W case, as long as we can’t divide cleanly into h by w squares, we can fulfill such need. We can prove by constructing one solution for all such cases.

Construction

We will assume sum of each h by w rectangel is -1. Then total number of complete squares ncs= W/w * H/h. Number of padding cells npc = H * W - ncs * h * w.

So we can fill each cell by value v = ncs/npc + 1, when i % h != h-1 || j % w != w- 1 Otherwise, we fill the cell by value -v * (h * w - 1) - 1