수열의 분할

길이가 $n$인 정수 수열 $A = (a_1, \ldots, a_n)$이 주어진다. $m$개의 정수 수열 $B_1, \ldots, B_m$ ($m \ge 1$)이 다음 두 조건을 모두 만족하면 $(B_1, \ldots, B_m)$을 $A$의 분할이라고 부른다.

• 각 $B_i$ ($1 \le i \le m$)는 길이가 1 이상인 정수 수열이다.
• $B_1, \ldots, B_m$을 이 순서대로 이어 붙이면 $A$와 같다.

예를 들어 $(3, 1, 4, 1, 5)$, $((3), (1, 4), (1, 5))$는 모두 $(3, 1, 4, 1, 5)$의 분할이다.

정수 수열 $B$에 대해 $B$ 원소 합의 제곱을 $f(B)$라고 한다. $A$의 분할 $(B_1, \ldots, B_m)$에 대해 $f(B_1) + \cdots + f(B_m)$을 이 분할의 점수라고 부른다. 예를 들어 $((3), (1, 4), (1, 5))$의 점수는 $3^2 + (1+4)^2 + (1+5)^2 = 70$이다.

$A$의 분할은 정확히 $2^{n-1}$개 있다. $A$의 모든 분할에 대한 점수를 내림차순으로 정렬했을 때 $k$번째 값을 구하라.

입력은 여러 개의 데이터셋으로 이루어진다. 데이터셋의 수는 30을 넘지 않는다. 각 데이터셋은 다음 형식으로 주어진다.

$n$ $k$

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

$n$과 $k$는 정수이며 $1 \le n \le 1000$, $1 \le k \le \min\{2^{n-1}, 2000\}$을 만족한다. 각 $a_i$는 수열 $A$의 $i$번째 원소인 정수이며 $-10^6 \le a_i \le 10^6$을 만족한다.

입력의 끝은 0 0 한 줄로 나타낸다.

각 데이터셋에 대해 $A$의 모든 분할 점수 중 $k$번째로 큰 값을 한 줄에 출력하라.