题目内容

给定两个整数 $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)$

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

输入

5 2 1 0 1
1 3 2 4 5

输出

说明

在这个样例中:

最优划分为 $[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$ 。

输入

3 3 1 0 1
10 20 30

输出

说明

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