题目描述

你有一个序列长度为 $n$ 的序列 $a$！初始时序列只有两端有隔板，其他位置没有。

你可以插入任意多个隔板，隔板不重合，且隔板不起到分割序列的作用。插入后，选择至多 $k$ 对 可以不相邻 的隔板，将他们之间的序列元素翻转。它们之间的隔板的位置不受影响，只改变元素位置，要求一个元素至多被翻转一次。

如果两个隔板相邻且他们之间的元素下标是 $l$ 到 $r$，则会对总贡献产生的权值为：$\sum\limits_{i=l}^{r} a_i \times (i - l + 1)$。求操作后的总贡献的最大值。

输入格式

第一行两个整数 $n$ 和 $k$。

第二行 $n$ 个整数表示最开始的序列 $a$。

输出格式

输出一行整数，代表操作后总贡献的最大值。

10 1
1 1 5 -4 -7 4 -8 0 -3 2 

10

提示

【样例解释 $\mathbf 1$】

序列初始两端各有一个隔板。在序列第 $2$ 个位置，第 $7$ 个位置，第 $8$ 个位置后添加隔板。并将第 $1$ 个位置到第 $7$ 位置中间的元素翻转。最后得到的序列权值为 $10$。可以证明不存在比这更大的权值。

【样例解释 $\mathbf 2$】

本题提供大样例，该数据满足 Subtask 3 的限制。具体求解不做解释。

【数据规模与约定】

本题开启子任务捆绑测试。本题自动开启 O2 优化。

• Subtask 1（15 pts）：$n\leq 20$。
• Subtask 2（45 pts）：$n\leq 100$。
• Subtask 3（40 pts）：$n\leq 550$。

对于所有测试点满足 $1\leq n \leq 550$，$1\leq k \leq n$，$-10^9 \leq a_i \leq 10^9$。