Using a 2-D prefix sum array, we can calculate the total number of scales in any rectangle in ~\mathcal{O}(1)~. For a rectangle with its top left corner at ~(a,b)~ and its bottom right corner at ~(c,d)~, we can use inclusion-exclusion to see that the total number of scales = ~prefix[c][d] - prefix[a][d] - prefix[c][b] + prefix[a][b]~.

Brute forcing all possible rectangles gives us an ~\mathcal{O}(W^2 \times H^2)~ solution, which will give us ~50\%~ of the points. To get ~100\%~, we need to make the insight that since all cells have a non-negative number of scales, we only need to consider the number of scales in the rectangle with maximum length with each possible width.

Time Complexity: ~\mathcal{O}(W \times H \times \min(W, H))~