问题描述

给定一个长度为 $N$ 的正整数序列 $A_{1\sim N}$ 和一个正整数 $M$，现要将其分成连续的 $K(1\le K \le M)$ 段，对于分完之后的下标为 $[l, r]$ 的一段，它的滑稽值为下标不同的数两两相乘求和，可以表示为 $\sum_{i = l}^{r}\sum_{j =i + 1}^{r}A_i\cdot A_j$。

现在请问如何分段可以使得最大的一段的滑稽值最小，并输出这个值。

输入格式

输入一行包含 $2$ 个数 $N, M$，分别为序列的长度和最大可以分成的段数。

第二行包含 $N$ 个空格隔开的正整数，为序列 $A$。

$(1 \leq M \leq N \leq 200000,1 \leq A_i \leq 10000)$

输出格式

输出仅一行，包含一个整数，表示答案。

样例输入

6 3
1 4 7 2 5 8

样例输出

39

说明

我们可以把序列分成 $\text{[1,4,7],[2,5],[8]}$，这样最大的一段滑稽值为 $39$，是最小的分法。