题目内容

给定两个整数$b,c$和一个长度为$n$的数组$a$。

你需要将数组$a$划分为$m$个连续子数组，覆盖全部元素且互不重叠每段长度至少为$k$。

我们定义一段数组的贡献为：从该段中删除任意$k$个数后，剩余元素贡献之和。设该段的原始长度为$len$(删除前的长度)，其中每个元素$a_i$的贡献定义为：

$c×len^2×(a_i-b)^2$

请问：如何划分才能使得所有段的总贡献最大？输出该最大贡献值。

输入描述

第一行输入五个整数$n(1≤n≤1000)$、$m (1≤ m ≤ min(n, 100))$、 $k (1 ≤ k≤ min(n, 100))、b$和$c$，含义如下:

• $n$为数组长度

• $n$为划分的段数

• $k$为每段需要删除的元素个数;

• $b,c$为题面参数。

  第二行输入n 个整数 $a_1,a_2,...,a_n(-100≤a_i≤100)$,表示数组元素。 保证$m×k≤n$。

  数据范围：$(1≤n≤ 1000, 1≤m≤ min(n,100),1≤k≤(n,100),m×k≤n,-100≤a_i,b,c≤100)$

输出描述

输出一个整数，表示最大的总贡献值。

样例1

输入

5 2 1 0 1
1 3 2 4 5

输出

800

说明

在这个样例中:

• 最优划分为$[1]$与[$3,2,4,5]$；
• 在第一段删除元素$1$，该段无剩余元素，贡献为$0$
• 在第二段删除最小元素$2$，剩余元素$[3,4,5]$，段长度为$4$，贡献为 $1×4^2 ×3^2 +1×4^2 ×4^2 +1×4^2×5^2=144+256+400=800$

总贡献为$0十800=800$。

样例2

输入

3 3 1 0 1
10 20 30

输出

0

说明

当每段长度为$1$目需要删除$1$个元素时，各段无剩余元素，因此总贡献为$0$