Maximizing Carnival Game Rewards

Ringo is participating in a carnival event in Singapore. He has a collection of tickets in his pocket. The tickets come in n different colors (where n is an even number); every ticket is painted in one of the n colors and has a nonnegative integer printed on it. For the color i (0 ≤ i ≤ n-1) there are m tickets, and they are given in non-decreasing order. In other words, the number on the j-th ticket of color i is x[i][j] (0 ≤ j ≤ m-1). Note that numbers on tickets of different colors may be equal.

The carnival game is played in k rounds (rounds are numbered 0 to k-1). In each round the following occurs:

1. Ringo selects exactly one ticket from each color, forming a collection of n tickets.
2. The game host records the numbers on the selected tickets, say a[0], a[1], ..., a[n-1]. The order of these numbers is not relevant.
3. The host then draws a special card from a lucky box. The card has an integer b printed on it. However, Ringo has noticed a nefarious trick: the host actually chooses b in such a way that it minimizes the reward for that round.
4. For each ticket number a[i] in the collection, the absolute difference |a[i] − b| is computed, and their sum is calculated as S = Σ_i=0^n-1|a[i] − b|. This sum S is the reward Ringo gets for that round.
5. After the round ends, all n tickets used in that round are discarded and cannot be used in future rounds.

After k rounds, Ringo discards any remaining tickets. Knowing the trick with the lucky box, Ringo wants to design a ticket allocation strategy that assigns one ticket per round from each color (thus exactly k tickets per color are used) so that his total reward (i.e. the sum of the rewards over all rounds) is maximized.

It is known that when the host chooses the card number b in a round, he minimizes the round's reward. For a given round with ticket numbers sorted in non-decreasing order, the host can choose any b between the two middle numbers (since n is even) so that the round reward becomes the difference between the sum of the larger half and the smaller half of the numbers. Thus, if the selected ticket numbers sorted are a[0] ≤ a[1] ≤ ... ≤ a[n-1], the reward for that round is:

\( S = \sum_{i=n/2}^{n-1} a[i] - \sum_{i=0}^{n/2-1} a[i] \).

Your task is to implement the function find_maximum as described below to compute the maximum total reward Ringo can get by choosing an optimal ticket allocation strategy. In doing so, you must call the function allocate_tickets exactly once to output one optimal allocation.

Function Specification

• long long find_maximum(int k, std::vector<std::vector<int>> x)

Parameters:

• k: the number of rounds in the game.
• x: an n×m matrix where the i-th row represents the ticket numbers for the i-th color in non-decreasing order.

You have additional helper function available:

void allocate_tickets(std::vector<std::vector<int>> s)

The array s is an n×m matrix where if the j-th ticket of color i is allocated to round r, then s[i][j] = r; otherwise, it is set to -1. For each color i, every round number from 0 to k-1 must appear exactly once among s[i][0], s[i][1], ..., s[i][m-1] (the remaining positions should be -1).

If there are multiple optimal strategies, you may output any one of them.

inputFormat

The first line contains three integers: n (the number of colors, an even number), m (the number of tickets per color), and k (the number of rounds), where 1 ≤ k ≤ m. The following n lines each contain m nonnegative integers. The i-th line represents the ticket numbers for the i-th color in non-decreasing order.

outputFormat

Output a single integer: the maximum total reward Ringo can achieve with an optimal allocation strategy.

sample

2 2 1
1 3
2 4

3

</p>