Actually, there is nothing to spoil in this task. It is perhaps the only problem that could be solved by the guys from the military academy. The only possible solution is already told in the task. Every location on the map should be checked for almost every characteristic. Actually, a good optimization comes from that "almost every characteristic", it will be discussed later.

It is easy to estimate that there is no way to calculate ~1000~ characteristics at every location of the ~1000 \times 1000~ map in time, by simply summing the values inside every characteristic. However, it is possible to calculate every characteristic a little bit faster – in constant time. Consider the following green characteristic anywhere on the map.

There are six rectangles in the picture. Every rectangle starts at the top left corner of the map and continues to the corner with a red number – rectangle id. The altitude map can be converted to the map of summed values in all possible rectangles of this type. The converting can be done in linear time. Furthermore, a sum of values in any rectangle (of any type) on the map can be calculated in a constant time. For example, sum of values in a dark green rectangle can be calculated by ~(3)-(1)-(2)+(0)~, where ~(X)~ means the sum of values in precalculated rectangle ~X~. Similar, in light green rectangle – by ~(5)-(3)-(4)+(2)~.

To calculate a characteristic, the average value of altitude in the green rectangles should be compared. The comparison can always be converted to the difference that is compared to zero, in the example:

$$\displaystyle \begin{align*} (\text{dark green})-(\text{light green}) &= (3)-(1)-(2)+(0)-((5)-(3)-(4)+(2)) \\ &= 2 \times (3) - (1) - 2 \times (2) + (0) - (5) + (4) \end{align*}$$

That's how the characteristics can be calculated in a constant time.

One more optimization that was mentioned earlier is possible. We are looking for the location where maximum altitude requirements of the characteristics are met. We can skip checking the characteristics at every location, if number of the characteristics that are left to check at that location summed with the number of already calculated characteristics that met the altitude requirement cannot exceed the maximum number of good characteristics found till now.