时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
实验室里一直流传着一个传说，在半夜凌晨无人之时，某一台关闭着的显示器会突然亮起，并且传来噼里啪啦敲击键盘的声音......
某一天夜里，实力羸弱乖巧懂事但是贼皮的学弟wzc一个人躺在实验室的床上玩着手机，突然耳边传来了噼里啪啦敲击键盘的声音。
“d巨巨？”wzc还以为是目前实验室最强的男人半夜跑回来写题了，但是他惊讶的发现d巨巨的座位上坐着一个从未见过的半透明的人。
“我是你上上上....上上上届的学长，辛苦训练了两年但是因为自己太菜最后连一块铜都拿不到，所以灵魂一直徘徊在实验室里想完成自己拿铜的夙愿。”半透明的学长如是说道，“学弟我看你骨骼精奇，但是如果没有贵人相助，最后也只能落得一个和学长一样专业打铁的下场。”
“但是现在学长为你带来了自己钻研多年得到的n份秘药，可以增加你的码力值。每份秘药都有一个系数值，你必须按照给定的顺序依次把他们分成若干天吃完，每天至少吃k份秘药并且必须在若干天后能把所有秘药都吃掉，每天你能增加的码力值是你当天吃的最后三份秘药的系数值的乘积，减去当天吃的最早三份秘药的系数值的乘积。“
wzc感激涕零得收下了这n份秘药，但是问题来了，他要怎么划分这n份秘药，才能尽可能多得增加自己的码力值呢？wzc想不不来（如果想得出来还能被说是打铁的料？）只好来求助机智的你了。
输入描述:
输入数据的第一行包含两个整数n和k代表有n份秘药，每天至少要按照给定的顺序吃掉k份。（3≤k≤n≤1×107）
第二行包含了用空格隔开的n个整数ai代表依次给定的每份秘药的系数值。（-3×103≤ai≤3×103）
输出描述:
输出一个整数，代表wzc可以利用这些秘药增加的最大码力值。
示例1
说明
总共4份秘药，每天至少吃3份，因此只能在第一天吃完所有的秘药。码力值增加3×9×(-1)-2×3×9=-81。（？？？这什么鬼学长？？？，奥本来就是鬼啊那没事了。）
示例2
输入
复制
9 3
-1 -2 -3 -4 -5 -6 -7 -8 -9