3082 - 魔法环

小 M 面临着激发自己魂器——魔法环的任务。

魔法环上有 n 个节点，每个节点上都有一个魔法精灵，每个魔法精灵都有一个固定的魔供值，这些魔供值形成一个 0 \sim n-1 的排列。

小 M 可以选择激活或不激活一个魔法精灵，但为了激发魔法环，必须至少激活 k(\ge 2) 个魔法精灵。

每个魔法精灵无论是否激活都会产生附魔值：

• 对于一个被激活的魔法精灵，它产生的附魔值为它的魔供值的平方。
• 对于一个未被激活的魔法精灵，它会在环上朝左右看，分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」，产生的附魔值为这个「目标精灵」的魔供值与看向这个「目标精灵」时视线经过的距离的乘积。

作为新手，小 M 希望在激活魔法环的前提下，使得所有魔法精灵的附魔值之和最小，从而更好地控制魔法环的能量。

第一行两个整数 n,k。

第二行 n 个整数，表示每个节点上魔法精灵的魔供值。

一行一个整数，表示最小附魔值之和。

【样例 1 解释】

激活魔供值为 0 和 1 的魔法精灵。

• 魔供值为 3 的魔法精灵，选择魔供值为 1 的魔法精灵，产生的附魔值为 1 \times 3 = 3。
• 魔供值为 0 的魔法精灵被激活，产生的附魔值为 0^2=0。
• 魔供值为 1 的魔法精灵被激活，产生的附魔值为 1^2=1。
• 魔供值为 4 的魔法精灵，选择魔供值为 1 的魔法精灵，产生的附魔值为 1 \times 1 = 1。
• 魔供值为 2 的魔法精灵，选择魔供值为 1 的魔法精灵，产生的附魔值为 1 \times 2 = 2。

总共产生的附魔值为 7。

对于所有数据，2\le k \le n \le 3000，k \le 100，每个节点上魔法精灵的魔供值形成一个 0\sim n-1 的排列。

MGOI