The above image shows the division of the region into states. The corresponding sum of squares of the row sums of the state sizes for each cell is 408951.

Congrats to everyone who found the solution!