Minimizing Daily Journey Variance

Pine embarks on a journey from (S) to (T) that is divided into (n) segments. The transition points between segments are equipped with rest stops. Pine plans to finish the journey in (m) days. However, except for the last day, he must stop at one of the designated rest stops by the end of each day, meaning that a segment must be completely traversed within the same day.

To keep his daily travel distances as similar as possible, Pine wants to partition the (n) segments into (m) contiguous groups (each group representing one day’s travel) so that the variance of the daily distances is minimized. Let the distance traveled on day (i) be (x_i) and the total distance be (L = \sum_{i=1}^{m} x_i). The variance of the daily distances is defined as [ v = \frac{1}{m} \sum_{i=1}^{m} \left(x_i - \frac{L}{m}\right)^2. ] It can be proven that (v \times m^2) is an integer. To avoid precision issues, output (v \times m^2) as the final result.

Note that since (L) is fixed, minimizing (v \times m^2) is equivalent to minimizing (m\sum_{i=1}^{m} x_i^2 - L^2). In other words, if you partition the segments so that the sum of squares of the daily distances is minimized, then the answer will be [ \text{Answer} = m \times \Big(\sum_{\text{days}} (\text{day distance})^2\Big) - L^2. ]

Input and output descriptions are provided below.

inputFormat

The first line contains two integers (n) and (m) where (n) is the total number of segments and (m) is the number of days. The second line contains (n) positive integers representing the lengths of each segment in order.

outputFormat

Output one integer, which is (v \times m^2), where (v) is the minimum variance of the daily travel distances.

sample

3 2
1 2 3

0