【模板】wqs二分1

题目描述

你有一个序列,你需要把它分成最多 $K$ 段。 对每一段均计算其中所有数之和,将其平方计为这一段的分值。 每一段的分值之和就是这种分法的扣分。请问你最少扣多少分?

输入输出格式

输入格式


第一行两个数 $n$,$K$,表示序列的长度和段数的限制 第二行有 $n$ 个数,表示这个序列。

输出格式


输出一个数,表示最优分法的扣分。

输入输出样例

输入样例 #1

5 3
1 10 4 2 8

输出样例 #1

221

说明

对于30%的数据:$ n \leq 1000 $ 对于100%的数据:$ 2 \leq K < n \leq 100000 $,序列中的数均不超过$50$。