Partitioning a Sequence by Score

Given an integer sequence $A = (a_1, \ldots, a_n)$ of length $n$, call $(B_1, \ldots, B_m)$ a partition of $A$ ($m \ge 1$) when both of the following hold.

• Each $B_i$ ($1 \le i \le m$) is an integer sequence of length at least 1.
• Concatenating $B_1, \ldots, B_m$ in this order gives $A$.

For example, $(3, 1, 4, 1, 5)$ and $((3), (1, 4), (1, 5))$ are both partitions of $(3, 1, 4, 1, 5)$.

For an integer sequence $B$, let $f(B)$ be the square of the sum of the elements of $B$. For a partition $(B_1, \ldots, B_m)$ of $A$, the score of the partition is $f(B_1) + \cdots + f(B_m)$. For example, the score of $((3), (1, 4), (1, 5))$ is $3^2 + (1+4)^2 + (1+5)^2 = 70$.

$A$ has exactly $2^{n-1}$ partitions. Sort the scores of all partitions of $A$ in descending order and find the $k$-th value.

The input consists of multiple datasets. The number of datasets does not exceed 30. Each dataset is given in the following format.

$n$ $k$

$a_1$ $a_2$ $\ldots$ $a_n$

$n$ and $k$ are integers with $1 \le n \le 1000$ and $1 \le k \le \min\{2^{n-1}, 2000\}$. Each $a_i$ is the $i$-th element of $A$, an integer with $-10^6 \le a_i \le 10^6$.

The input ends with a line containing two zeros.

For each dataset, print on one line the $k$-th largest score among all partitions of $A$.