Note that if the last enemy to destroy has power equal to x, the sum of powers of all enemies is 2x. Therefore to find the power of the enemy to destroy last, let us find the sum of all powers and divide it by two. After that just pick any enemy with such power and swap it with the last one.

Let us process passengers one by one. Since Pink Ranger could take any seat, any passenger can be Pink Ranger.

For each seat we want to be able to quickly answer if it is free. Let us use std::set that stores the set of occupied seats. To check whether the current passenger can be Red Ranger let us find the seat that Red Ranger would choose. Iterate row from 1 to n, and if there is a free seat in the current row, take the left seat if it is free, or the right seat in the other case. If the current passenger chose that seat, he could be Red Ranger. Similarly we can check whether the current passenger could be Blue, Black or Yellow Ranger. After processing the passenger, add the seat he chose to the set of occupied seats.

The solution described uses O(nk) time and O(k) memory.

To get rid of time limit, let us note that all we need is to store the minimal and the maximal row that have free seats. Use two indices first and last to store them. Initially first = 1, last = n. After each passenger update these values. Increase first by 1, until the row pointed by first is completely occupied, then similarly decreaser last. There are at most k / 2 occupied rows, so both indices will be changed O(k) times.

Precalculate arrays: R[a][b] — the number of red details that have the first digit of the model number equal to a and the last digit equal to b; G[a] — the number of green details that have the last digit equal to a; и B[b] — the number of blue details that have the first digit equal to b.

It model numbers of different colors were distinct, the answer would be equal to the sum for all a and b of values G[a]·R[a][b]·B[b].

To resolve the situation when some pair of details have the same model number, calculate the number of red-blue pairs with the same model number, red-green pairs and green-blue pairs. Note that only model numbers with the same first and last digit need to be considered. You can use std::map to calculate the number of such model numbers. Now use inclusion-exclusion principle to find the answer: subtract the number of pairs of each type and add back twice the number of triples that all three rangers use detail with the same model number.

Let us use dynamic programming with mask of the last two columns as a state. Consider for example subtask of calculating the maximal number of knights.

Let dp[i][mask_prev][mask_cur] be the maximal number of knights that can be positined among the first i columns, where mask_cur is the mask of the i-th column, mask_prev is the mask of the (i - 1)-th. Use bit equal to 1 to denote a knight and 0 to denote a knave.

Try all possible masks for the (i + 1)-th column, check whether constraints for the soldiers in the i-th column are satisfied, because now we know all of their neighbors.

The first and the last columns must be considered separately, because soldiers there don't have one of the neighbors.

Initial values: dp[2][mask_prev][mask_cur] the number of ones in mask_prev and mask_cur, if mask_prev can be before mask_cur.

Updating values: relax dp[i + 1][mask_cur][mask_next] with dp[i][mask_prev][mask_cur] + ones(mask_next), where ones(x) is the number of ones in x.

The answer is the maximum among dp[k][mask_prev][mask_cur], such that mask_cur can be after mask_prev.

Finally, we probably need to consider k = 1 separately, because there is no previsous column for any column in this case.

Let us give a sketch of the main solution idea. First, separately consider all parallelepipeds that have two or three equal sides. This can be done in O(n).

Now let us consider the case where all three sides are different. Let us build the following undirected graph: vertices are side length, connect a and b if there are at least two sheets of size a × b. Now the problem is reduced to considering all triangles in this graph which can be done in O(n² / w) or O(nsqrt(n)) time (here w is the word size, 32 or 64 which comes up from bit compression).