U472925 小 Y 之衣柜

小 Y 现在在放衣服。

现在小 Y 的衣柜一共有无限层，长度为 $n$，而且每层只能放一件衣服。而小 Y 的衣服也有无数件，这些衣服每一件长度为 $m$。 对于衣柜上的每一列，小 Y 都有一个满意值 $a_i$，如果放在这一列上的衣服有**奇数**个，则小 Y 就会增加 $a_i$ 点满意值。 现在小 Y 想知道他所能够最后得到的最大满意值是多少。 #### 简要题意： 给定一个全 $0$ 序列 $s$ 和序列 $a$，长度都为 $n$，每一次你都可以在序列 $s$ 中选择一个固定长度 $m$ 的区间翻转这段区间里面的每一个数，可以选择无数次。最后得到的答案是 $\sum_{i=1}^{n} s_{i} \times a_{i} $，目标是其答案最大。

第一行，两个整数 $n,m$。 第二行，$n$ 个整数，表示小 Y 对每一列的满意值。

输出能得到的最大满意值。

$1 \le n \le 10^5$ $1 \le m \le 8$ $0 \le \left| a_i \right| \le 10^9$ 保证 $m \le n$。