问题描述

给定一个长度为 $N$ 的正整数序列 $A_{1 \sim N}$，需要将其划分为连续的 $M$ 段。对于划分后的一段（下标范围为 $[l, r]$ 的子数组），其滑稽值定义为下标不同的数两两相乘的和，可以用公式表示为：

$$\text{滑稽值} = \sum_{i=l}^{r} \sum_{j=i+1}^{r} A_i \cdot A_j $$

现在的任务是：通过合理划分序列，使得划分后的所有段中滑稽值最大的一段的滑稽值尽可能小，并输出这个值。

换句话说：

• 要求对序列进行划分，使得所有划分中滑稽值的最大值达到最小化。
• 输出这个最小化后的最大滑稽值。

若区间中只有一个数，滑稽值为 $0$。

输入格式

输入一行包含 $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