Minimize Segmented Sequence Value

Given a sequence of n integers, you are required to partition it into m contiguous segments. For any segment with elements (x_1, x_2, \ldots, x_k), its value is defined using the formula:

[ V = \frac{\left(\left(\sum_{i=1}^{k} x_i \times \bar{x}\right)+\bar{x}\right)^2}{\bar{x}^2} ]

where (\bar{x}) is the average of the segment, i.e., (\bar{x} = \frac{\sum_{i=1}^{k}x_i}{k}). With a simple manipulation, note that if we let (S = \sum_{i=1}^{k}x_i), then (\bar{x} = \frac{S}{k}). Substituting and simplifying the expression, we obtain:

[ V = (S+1)^2 ]

Your task is to partition the given sequence into m contiguous segments such that the sum of the values of each segment, (\sum (S+1)^2), is minimized. Output the minimum possible total value.

inputFormat

The first line contains two integers n and m, where n is the number of elements in the sequence and m is the number of segments. The second line contains n space-separated integers, representing the sequence.

outputFormat

Output a single integer, the minimum possible total value when the sequence is partitioned into m contiguous segments.

sample

5 2
1 2 3 4 5

149