### 问题描述 当深秋的苹果树丰收时，村庄的居民们兴致勃勃地采摘着红彤彤的苹果。他们将采摘下来的 $N$ 个苹果排成了一排，形成了一个苹果序列 $A$，第 $i$ 个苹果的甜度值为 $A_i$（$1\le i\le N$）。 现在村民需要将苹果序列划分为连续的 $M$ 段，对于分割后的某一段 $A_{l\sim r}$，定义其**美味值**表示为该段内不同下标的苹果的甜度两两相乘的总和，即 $\sum_{i = l}^{r}\sum_{j =i + 1}^{r}A_i\cdot A_j$。 注：如果某一段只有一个苹果，它的美味值为 $0$。 请问应当如何给苹果分段，才能使得美味值最大的一段尽可能小，你只需要输出这个最大美味值可能的最小值即可。 ### 输入格式 第 $1$ 行输入 $2$ 个正整数 $N, M$，分别为苹果序列的长度和需要分成的段数。 第 $2$ 行输入 $N$ 个空格隔开的正整数，表示苹果序列。 ### 输出格式 输出仅 $1$ 行，包含 $1$ 个整数，表示答案。 ### 样例输入 ```text 6 3 1 4 7 2 5 8 ``` ### 样例输出 ```text 39 ``` ### 说明 我们可以把苹果序列分成 $\text{[1,4,7],[2,5],[8]}$，这样最大的一段美味值为 $39$，是最小的分法。 ### 评测数据规模 $1 \leq M \leq N \leq 200000$。 $1 \leq A_i \leq 10000$。