Flight Boarding Optimization

Peter runs boarding at the Byteland airport, and his job is to make boarding faster. Planes in Byteland have $s$ rows, numbered $1$ through $s$ starting at the front. Every row has six seats, labeled A to F.

The $n$ passengers stand in one queue and board the plane one at a time. If passenger $i$ sits in row $r_i$, that passenger's boarding difficulty is the number of passengers who boarded earlier and sit in rows $1$ through $r_i - 1$. The total boarding difficulty is the sum of the difficulties of all $n$ passengers. For example, take ten passengers whose seats in queue order are 6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A. Their difficulties are 0, 0, 0, 2, 0, 2, 0, 7, 7, 5 and the total is 23.

To speed boarding up, Peter divides the plane into $k$ zones. Every zone is a continuous range of rows. Boarding then runs in $k$ phases. In each phase Peter calls one zone, and the passengers seated in that zone board in their original queue order. Peter also decides which zone each phase calls.

Take the queue above and split the plane into two zones, rows 5 to 10 and rows 1 to 4. The first phase seats 6A, 5F, 10E, 8B, 5A and the second phase seats 4B, 2E, 2A, 3F, 1C, in that order. The total boarding difficulty is 6.

Given the queue, find the division into $k$ zones that minimizes the total boarding difficulty and report that minimum.

The first line contains three integers $n$, $s$, and $k$ ($1 \le n \le 1000$, $1 \le s \le 1000$, $1 \le k \le 50$, $k \le s$).

The second line contains $n$ integers $r_1, r_2, \ldots, r_n$ ($1 \le r_i \le s$), where $r_i$ is the row of the $i$-th passenger in the queue.

At most 6 passengers sit in any single row.

Print the minimum possible total boarding difficulty.