时间限制：1秒　　内存限制：256M

---

【题目描述】

　　白鸟将飞过天空中排成一线的 𝑛 个梦想，编号从 1 到 𝑛，白鸟必须从梦想 1 出发，最终到达梦想 𝑛。每个梦想有它的价值 𝑎𝑖，当白鸟没有直接飞过该梦想而是停下来见证了它的实现，则它会带上该梦想的价值继续飞行。每一次飞翔的距离不能超过 k。并且白鸟需要恰好见证 𝑚 个梦想（包括起点和终点）。
　　每次飞翔会获得一个价值，价值由两部分组成：
　　　• 基础价值与飞行距离成正比，比例系数为 𝑝；
　　　• 如果本次飞行的起点和终点的梦想编号奇偶相同，则得到额外价值为 𝑟，否则为 𝑠。
　　即从 𝑖 飞行到 𝑗 能得到的价值为：

　　其中 otherwise 的意思是否则；𝑖≡𝑗 (mod2) 的意思是 𝑖 除以 2 的余数等于 𝑗 除以 2 的余数。
　　白鸟携带的总价值为所有经过的梦想的价值之和加上所有飞行的价值之和，求白鸟到达终点时的最大携带价值。

【输入格式】

　　本题有多组测试数据。
　　第一行为两个整数 𝑐,𝑇，代表子任务编号和测试数据组数（特别的务编号𝑐=0）。
　　对于每组数据输入格式如下：
　　第一行为六个整数 𝑛,𝑚,𝑘,𝑝,𝑟,𝑠，含义如上。
　　第二行为 𝑛 个整数 𝑎1,𝑎2,...,𝑎𝑛，代表每个梦想的价值。

【输出格式】

　　对于每组数据输出一行，即白鸟到达终点时能够携带的最大总价值。如果无法通过恰好 𝑚 个梦想到达终点，输出 −1。

【输入输出样例1】

　Input

0 1
6 4 2 1 2 3
5 3 2 4 6 8

　Output

33

【样例说明】

　　最大方案 1→3→5→6，最终价值为 33。

【输入输出样例2】

　Input

0 1
4 3 2 1 2 3
1 2 3 4

　Output

16

【输入输出样例3】

　Input

0 1
5 3 3 10 20 30
‐5 ‐3 ‐1 2 4

　Output

101

【数据限制】

　　对于所有数据：\(1≤𝑇≤10,1≤𝑘≤𝑛≤10^6,2≤𝑚≤10^2,1≤|𝑎𝑖|,|𝑟|,|𝑠|≤10^9,1≤|𝑝|≤10^5\)。
　　所有测试数据的范围和特点如下表所示：

　　其中，“特殊性质”一列中的数字意义如下：
　　• 特殊性质 1：保证 𝑚=2；
　　• 特殊性质 2：保证 𝑘=𝑛；
　　• 特殊性质 3：保证 𝑟=𝑠。

【来源】

　　Mr.he