数列の分割
시간 제한8초메모리 제한1024 MB
주어진 수열을 인접한 조각들로 나누는 2^(n-1)가지 방법 각각에 대해 각 조각 합의 제곱을 모두 더한 점수를 구하고, 그중 k번째로 큰 값을 찾는다.
문제
長さ n の整数列 A = (a1, ...,an) が与えられる．m 個の整数列 B1, ..., Bm (m ≥ 1) が以下の条件をともに満たすとき，(B1, ..., Bm) を A の分割と呼ぶことにする．
- いずれの Bi (1 ≤ i ≤ m) も，長さが 1 以上の整数列である．
- B1, ..., Bm をこの順につなげたものは A に等しい．
たとえば，((3, 1, 4, 1, 5)) や ((3), (1, 4), (1, 5)) などはいずれも (3, 1, 4, 1, 5) の分割である．
また，整数列 B に対し，B の要素の総和の 2 乗を f(B) とする．さらに，A の分割 (B1, ..., Bm) に対し，f(B1) + … + f(Bm) を，この分割のスコアと呼ぶことにする．たとえば，((3), (1, 4), (1, 5)) のスコアは 32 + (1+4)2 + (1+5)2 = 70 である．
A の分割はちょうど 2n-1 個存在する．A のすべての分割に対するスコアを降順に並べたとき，k 番目となる値を求めよ．
たとえば，Sample Input の 2 つ目のデータセットでは，A の分割のスコアを降順に並べると 196, 130, 116, 110, 106, 100, 90, 70, 70, 68, 66, 62, 60, 60, 58, 52 となるため，6 番目の値は 100 である．
입력
入力は複数のデータセットからなる．データセットの個数は 30 を超えない．各データセットは次の形式で表される．
n k
a1 a2 … an
n および k はいずれも整数であり，1 ≤ n ≤ 1000 および 1 ≤ k ≤ min{2n-1, 2000} を満たす．各 ai は数列 A の i 番目の要素となる整数であり，-106 ≤ ai ≤ 106 を満たす．
入力の終わりは 2 つのゼロからなる行で表される．
출력
各データセットについて，A のすべての分割のスコアのうち k 番目に大きい値を，1 行に出力せよ．