비행기 탑승 순서 최적화

피터는 바이트랜드 공항에서 탑승 업무를 총괄하는 관리자다. 맡은 일은 탑승 절차를 최적화하는 것이다. 바이트랜드의 비행기에는 좌석 열이 $s$개 있고, 앞쪽부터 $1$번, $2$번, ..., $s$번으로 번호가 붙는다. 각 열에는 A부터 F까지 여섯 자리가 있다.

승객 $n$명이 한 줄로 서서 한 명씩 비행기에 오른다. $i$번째 승객의 좌석이 $r_i$번 열에 있으면, 이 승객의 탑승 난이도는 먼저 탑승한 승객 가운데 $1$번 열부터 $r_i - 1$번 열 사이에 앉은 사람의 수다. 전체 탑승 난이도는 승객 $n$명의 난이도를 모두 더한 값이다. 예를 들어 승객이 열 명이고 줄 순서대로 좌석이 6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A라면 각 승객의 난이도는 차례로 0, 0, 0, 2, 0, 2, 0, 7, 7, 5이고 전체 난이도는 23이다.

탑승을 최적화하려고 피터는 비행기를 구역 $k$개로 나눈다. 각 구역은 연속한 열 범위여야 한다. 그러면 탑승은 $k$단계로 진행된다. 각 단계에서 피터가 구역을 하나 부르고, 그 구역에 좌석이 있는 승객이 처음 줄 순서 그대로 탑승한다. 어느 단계에 어느 구역을 부를지도 피터가 정한다.

위 예에서 비행기를 5번 열부터 10번 열까지와 1번 열부터 4번 열까지 두 구역으로 나누면, 첫 단계에서 6A, 5F, 10E, 8B, 5A가 차례로 앉고 두 번째 단계에서 4B, 2E, 2A, 3F, 1C가 차례로 앉는다. 이때 전체 탑승 난이도는 6이다.

줄 순서가 주어질 때, 전체 탑승 난이도를 최소로 만드는 구역 $k$개 분할을 찾아 그 최솟값을 구하라.

첫째 줄에 정수 $n$, $s$, $k$가 공백으로 구분되어 주어진다 ($1 \le n \le 1000$, $1 \le s \le 1000$, $1 \le k \le 50$, $k \le s$).

둘째 줄에 정수 $r_1, r_2, \ldots, r_n$이 주어진다 ($1 \le r_i \le s$). $r_i$는 줄에서 $i$번째로 선 승객이 앉는 열 번호다.

한 열에 앉는 승객은 최대 6명이다.

가능한 전체 탑승 난이도의 최솟값을 한 줄에 출력한다.