P7084 [NWRRC 2013] Flight Boarding Optimization

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)$

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

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