题目描述

Peter is an executive boarding manager in Byteland airport. His job is to optimize the boarding process. The planes in Byteland have $s$ rows, numbered from $1$ to $s$ . Every row has six seats, labeled A to $F$ .

There are $n$ passengers, they form a queue and board the plane one by one. If the i-th passenger sits in a row $r_{i}$ then the difficulty of boarding for him is equal to the number of passengers boarded before him and sit in rows $1$ . . . $r_{i}−1$ . The total difficulty of the boarding is the sum of difficulties for all passengers. For example, if there are ten passengers, and their seats are $6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A,$ in the queue order, then the difficulties of their boarding are $0 , 0 , 0 , 2 , 0 , 2 , 0 , 7 , 7 , 5$ , and the total difficulty is $23$ .

To optimize the boarding, Peter wants to divide the plane into $k$ zones. Every zone must be a continuous range of rows. Than the boarding process is performed in $k$ phases. On every phase, one zone is selected and passengers whose seats are in this zone are boarding in the order they were in the initial queue. $$

In the example above, if we divide the plane into two zones: rows $5-10$ and rows $1-4$ , then during the first phase the passengers will take seats $6A, 5F, 10E, 8B, 5A,$ and during the second phase the passengers will take seats $4B, 2E, 2A, 3F, 1C,$ in this order. The total difficulty of the boarding will be $6$ .

Help Peter to find the division of the plane into $k$ zones which minimizes the total difficulty of the boarding, given a specific queue of passengers.

输入格式

The first line contains three integers $n (1 \le n \le 1000) , s (1 \le s \le 1000)$ , and $k (1 \le k \le 50$ ; $k \le s)$ . The next line contains $n$ integers $r_{i} (1 \le r_{i} \le s)$ .

Each row is occupied by at most $6$ passengers.

输出格式

Output one number, the minimal possible difficulty of the boarding.

题目大意

题目描述

Peter是 Byteland 机场的高级登机管理人员。他的工作是优化登机流程。Byteland 中的飞机有$s$行，编号从1到$s$。每排有六个座位，标有$A$到$F$。

有$n$名乘客，他们排成一队，一个接一个地登上飞机。如果第$i$位乘客坐在第$r_i$排，那么，他登机的难度等于在他前面登机的并且坐在第1......$r_i$ $-$1排的乘客人数之和。

登机的总难度是所有乘客的登机难度之和。例如，如果有十名乘客，他们的座位分别是$6A、4B、2E、5F、2A、3F、1C、10E、8B、5A$，按照排队顺序排列，那么他们登机的难度分别是$0、0、0、2、0、2、0、7、7、5$，总难度是$23$。

为了优化登机，Peter希望将飞机划分成$k$个区域。每个分区都必须是连续的行数。然后分成$k$段执行登机流程。在每个阶段，选择一个区域，座位在该区域的乘客将按照他们在初始队列中的顺序登机。

在上面的示例中，如果我们将平面划分为两个区域：第 $5-10$ 行和第$1-4$ 行，则在第一阶段，乘客将依次就座$6A、5F、10E、8B、5A$。在第二阶段，乘客将依次就座$4B、2E、2A、3F、1C$。登机的总难度为$6$。

帮助Peter找到将飞机划分为$k$个区域的方法，在给定特定乘客队列的情况下，将登机的总难度降至最低。

输入格式

第一行包括三个整数$n(1≤n≤1000)$,$s(1≤s≤1000)$和$k(1≤k≤1000)$

第二行包括$n$个整数$r_i(1≤r_i≤s)$

输出格式

输出一行一个数，最小的登机总难度

10 12 2
6 4 2 5 2 3 1 11 8 5

6

提示

Time limit: 2 s, Memory limit: 256 MB.