Optimized Boarding Difficulty

Peter is an executive boarding manager at Byteland airport. The plane has \(s\) rows (numbered from \(1\) to \(s\)), and each row has 6 seats labeled A to F. There are \(n\) passengers queuing up. If the \(i\)-th passenger sits in row \(r_i\), then his boarding difficulty is the number of passengers boarded before him who are sitting in rows strictly less than \(r_i\). The total difficulty is the sum of the individual difficulties.

To optimize the boarding process, Peter wants to partition the plane into \(k\) zones. Every zone is a contiguous range of rows. The boarding is then performed in \(k\) phases. In each phase, one zone is selected and the passengers whose seats are in this zone board in the same order as they appeared in the original queue.

Before boarding, Peter can decide the division of rows into zones and can choose the order in which the zones board. Notice that if a zone covers rows with higher numbers than another zone, then boarding it before the other will not contribute to the difficulty of the latter phase, because the difficulty for a passenger is only increased by those already boarded who sit in rows strictly less than his row. In fact, the optimal strategy is to board zones in decreasing order of rows. That is, if you partition the rows as \[ [1, x_1], [x_1+1, x_2], \ldots, [x_{k-1}+1, s], \] then the optimal boarding order is to board the zone with rows \((x_{k-1}+1, s)\) first, then \((x_{k-2}+1, x_{k-1})\), and so on, so that there is no cross‐zone contribution to the difficulty.

For a given sub-zone with rows ranging from \(L\) to \(R\) (inclusive), the difficulty is computed as follows. Process the queue in order and consider only the passengers whose row \(r\) satisfies \(L \le r \le R\). For each such passenger, his difficulty is the number of passengers already processed in this sub-zone with a row number strictly less than \(r\). The total difficulty is the sum of these values.

Your task is to divide the plane into \(k\) contiguous zones so that when boarded (in the optimal phase order described above) the total boarding difficulty is minimized, and output this minimum difficulty.

Input/Output Format

See below.

inputFormat

The first line contains three integers \(n\), \(s\), and \(k\) where \(n\) is the number of passengers, \(s\) is the total number of rows, and \(k\) is the number of zones.

The second line contains \(n\) seat identifiers separated by spaces. Each seat identifier is a string consisting of an integer (the row number) immediately followed by a letter (the seat label). The seat label is not used in the calculation; only the row number is relevant.

outputFormat

Output a single integer — the minimum possible total boarding difficulty.

sample

10 10 2
6A 4B 2E 5F 2A 3F 1C 10E 8B 5A

6