Circular Spaceship Energy Absorber Partitioning

A circular spaceship is composed of N sequential compartments. The design length of the i^th compartment is \(L_i\). To power the spaceship, exactly K space energy absorbers have to be installed. According to theory, these absorbers should be placed as uniformly as possible on the spaceship's hull. In other words, you need to partition the N compartments into K parts (each part consisting of consecutive compartments in the circle) and assign one energy absorber per part.

Let \(s_i\) be the total length of the compartments in the i^th part. The goal is to minimize the variance of \(\{s_i\}\). Note that the variance is defined as \[ \text{Var} = \frac{1}{K} \sum_{i=1}^{K} \left(s_i - \frac{S}{K}\right)^2, \quad \text{where } S = \sum_{i=1}^{N} L_i. \] For convenience, you are asked to output the product of the minimum variance and \(K^2\), i.e., \[ \text{Answer} = K^2 \cdot \text{Var} = K \sum_{i=1}^{K} s_i^2 - S^2. \]

Note: Since the spaceship is circular, a segment may wrap from the end of the list back to the beginning.

inputFormat

The first line contains two integers N and K (1 ≤ K ≤ N).

The second line contains N integers \(L_1, L_2, \dots, L_N\) representing the lengths of the compartments.

outputFormat

Output a single integer which is the product of \(K^2\) and the minimum variance, i.e., \(K \sum_{i=1}^{K} s_i^2 - S^2\).

sample

5 2
1 2 3 4 5

9