Suppose that the top and the bottom borders of the rectangle are fixed, and we are to choose only the left and the right borders. Then we can in O(K) find a list of all the rectangles which are contained in our band, and also a list of all the rectangles having a part in our fixed strip. We can represent it as a sorted collection of segments [l, r], where l and r are x-coordinates of left and right borders of a rectangle.

                                                                                                                                          

If multiple segments in the collection have a common point, glue them to make a one long segment, and memorize that now it really represents two segments. Thus, after such a gluing we obtain a collection of segments, and for each segment in the collection we know the number of rectangles covered by it (if there is a rectangle in it not lying in the band completely, we threat this segment as if it contains an infinity number of rectangles). Now we can process all the free segments (located between neirbouring segments in ur collection) and count the number of ways to cover them by a segment including no more than three objects (for this we will memorize only free segments separated from the current one by not more than three objects).  

Thus, we already have the O(N^2 K) solution: to try all possible horisontal bands and to compute for each of them in O(K) the number of rectangles covering from 1 to 3 objects. Note that if, for instance, the top border of the band touch no object, then we can move it up or down, and the answer for the band wouldn't change. Hence we can take as a border of a band only those rows, which contain at least one square belonging to an object, and then multiply the obtained result by the distance to the closest "non-empty" strings from above and below.     

Thus, we get the solution working O(K^3) and not depending on the field size or the limit on the number of covered objects.