Exhaustive enumeration.

According to the definition, we have , which gives . Thus, we should find the maximum *r*_{1} and *p*_{1}, and minimum *p*_{2}.

At first, note that the rextangulars can only have size (2*a* + 1) × (2*b* + 1) and (2*c* + 1) × (2*d* + 1), where *a*, *b*, *c*, *d* starts from zero. Then, there are two cases that we should take into consideration.

1) One rectangular is completely contained by the other one. Without loss of generality, we assume that *a* ≥ *c* and *b* ≥ *d*. For a rectangular with size *a* × *b*, there are (*n* - (2*a* + 1) + 1) × (*m* - (2*b* + 1) + 1) different positions to put it within the board. The inner rectangular can have (*a* + 1) × (*b* + 1) different sizes. As we can swap these two rectangulars, there are in fact 2 × (*a* + 1) × (*b* + 1) feasible answers. Furthermore, when *a* = *c*, *b* = *d*, the “swapping operation” gives the same answer, and thus we have 2 × (*a* + 1) × (*b* + 1) - 1 different answers. Taking the different positions into consideration, the final answer is (*n* - (2*a* + 1) + 1) × (*m* - (2*b* + 1) + 1) × (2 × (*a* + 1) × (*b* + 1) - 1).

2) Two rectangulars form a “crossing”. We enumerate *a*, *b*, *c* and calculate *d* based on the target area size *s*. The remaining work is similar to case 1).

The main idea is greedy algorithm, and as each interval is independent, we only focus on one single interval.

1) *t*_{i} < *T*_{i}: At first, we should note that if there are more than one buses which satisfy *m*_{j} + *t*_{i} > *T*_{i}, where *m*_{j} denotes the number of students in the *j*-th bus, we can always achieve a better result by moving all the “extra” students to one single bus. For instance, if there are two buses with *m*_{j} + *t*_{i} > *T*_{i} and *m*_{k} + *t*_{i} > *T*_{i}, , the compensation fees will be *x*_{i}(*m*_{j} + *m*_{k}), while if we move *m*_{k} + *t*_{i} - *T*_{i} students to the *j*-th bus, the fees are reduced to *x*_{i}(*m*_{j} + *m*_{k} + *t*_{i} - *T*_{i}). Therefore, there can be either one single bus with *m*_{j} + *t*_{i} > *T*_{i} or no bus at all. We can compute the maximum *Y* satisfying *m* > *Y*(*T*_{i} - *t*_{i}), where *Y* means that if the number of buses is less than or equal to *Y*, then every bus should take *T*_{i} - *t*_{i} students except for one single bus taking all the remaining students. For any *y* ≤ *Y*, the total cost can be written as (*m* - (*y* - 1)(*T*_{i} - *t*_{i}))*x*_{i} + *y* × *cost*_{i}, which is a monotonic function. Thus, the minimum value is obtained either at *y* = 1 or *y* = *Y*. For any *y* ≥ *Y* + 1, the total cost is *y* × *cost*_{i} and the minimum value is (*Y* + 1)*cost*_{i}. Therefore, the global minimum value should be *min*(*m* × *x*_{i} + *cost*_{i}, (*m* - (*Y* - 1)(*T*_{i} - *t*_{i}))*x*_{i} + *Y* × *cost*_{i}, (*Y* + 1)*cost*_{i}).

2) *t*_{i} ≥ *T*_{i}: for this case, the total cost is always *m* × *x*_{i} + *y* × *cost*_{i}, and thus the minimum value is *m* × *x*_{i} + *cost*_{i}.

The main framework is “prefix” idea, i.e., we define a function *f*(*x*) to denote the number of feasible integers less than or equal to *x*. Thus, the required answer is *f*(*r*) - *f*(*l* - 1).

Suppose that we write *x* in a binary form, and it has length *len*. For instance, *len* = 3 when *x* = 7. Then, all the feasible answers must have a binary length *ilen* ≤ *len*, which gives the following two cases.

1) *ilen* < *len*: any periodic integer *y* satisfies the requirements, and thus contributes a feasible answer, since *y* < *x* always holds. For a given *ilen*, we find all its divisors. For instance, for a divisor *d*, it means the binary sequence should have a cycle of length *d*. As the head digit is always 1, we have 2^{d - 1} feasible integers. However, for any divisor *d*' > *d* of *ilen*, if *d*' is a multiple of *d*, i.e., *ilen*%*d*' = 0, *d*'%*d* = 0, all the 2^{d - 1} sequences will be counted again. The reason is that as long as the current sequence has a cycle of length *d*, then it also has a cylce of length *d*'. Therefore, we should decrease 2^{d - 1} when we calculate for *d*'.

2) *ilen* = *len*: different from case 1), only those periodic integers less than or equal to *x* should be considered. We still consider each divisor *d* of *ilen*, and find out the leftmost *d* binary digits, written as *a*_{1a}_{2}...*a*_{d}, where *a*_{i} = 0, 1. Note that *a*_{1} = 1 always holds, and thus we can always have *a*_{2a}_{3}...*a*_{d} - 1 different feasible answers. Be careful that we should check whether *a*_{2a}_{3}...*a*_{d} can serve as an extra answer or not. We can simply repeat *a*_{1a}_{2}...*a*_{d} with *d* times and see if it is less than or equal to *x*. If yes, we in fact have *a*_{2a}_{3}...*a*_{d} - 1 + 1 feasible answers. Similarly, we should decrease *a*_{2a}_{3}...*a*_{d} - 1 or *a*_{2a}_{3}...*a*_{d} - 1 + 1 when we compute for *d*'.