You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

CET-6 考试马上要开始了！现在，小智要开始备战 CET-6 了。

可是，他的单词功底太差了，于是他准备开始摆烂背单词。

可是，人脑的能力是有限的，小智的大脑每一天都会有一个记忆的上限，如果超过这个上限，再多的单词也记不下了。

有一天，小智在背单词的时候想到了一个问题，你能帮帮他吗？

题目描述

小智一共有 $n$ 个单词需要背，第 $i$ 个单词所拥有的「精神值」为 $a_i$。

小智每天的记忆力都是有上限 $m$ 的。如果小智在第 $i$ 天内背完了 $[l,r]$ 内的单词，那么这些单词将会占用小智 $C_i = \sum\limits_{j=l} ^ r a_j^2$ 的记忆力。

小智需要在最多 $k$ 天里把这些单词全部背完，他希望你在把这些单词背完的同时，让他每天需要的记忆力的最大值尽可能小。

也就是说，你需要将一个序列最多分为 $k$ 段，请你找到一个最小的 $m$，使得 $\forall 1 \leq i \leq k$，$C_i= \sum\limits_{j=l} ^ r a_j^2 \leq m$，其中 $l$，$r$ 为各段的左、右端点。

输入格式

第一行有两个整数 $n, k$，表示小智需要背的单词数量和小智需要背完单词的天数。

第二行有 $n$ 个整数 $a_i$，第 $i$ 个整数表示第 $i$ 个单词的「精神值」。($a_i$<=$a_{i+1}$)

输出格式

共一行。

输出一个整数 $m$，表示小智所需的最小记忆力。

样例 #1

样例输入 #1

5 1
1 2 3 4 5

样例输出 #1

55

样例 #2

样例输入 #2

4 2
1 2 3 4

样例输出 #2

16

提示

样例 1 解释

由于小智最多要在 1 天内背完单词，所以必须将这些单词一次性背完，代价为 $55$。

样例 2 解释

可以发现，当小智第 1 天背 $[1,3]$ 的单词，第 2 天背 $[4,4]$ 的单词时需要的记忆力最少，为 $4^2 = 16$。

数据规模与约定

对于所有测试点，保证 $1 \leq n \leq 1 \times 10^5$，$1 \leq k \leq n$，$1\leq a_i \leq 1\times 10^6$。(注意数据范围)