数列の分割

長さ n の整数列 A = (a₁, ...,a_n) が与えられる．m 個の整数列 B₁, ..., B_m (m ≥ 1) が以下の条件をともに満たすとき，(B₁, ..., B_m) を A の分割と呼ぶことにする．

• いずれの B_i (1 ≤ i ≤ m) も，長さが 1 以上の整数列である．
• B₁, ..., B_m をこの順につなげたものは A に等しい．

たとえば，((3, 1, 4, 1, 5)) や ((3), (1, 4), (1, 5)) などはいずれも (3, 1, 4, 1, 5) の分割である．

また，整数列 B に対し，B の要素の総和の 2 乗を f(B) とする．さらに，A の分割 (B₁, ..., B_m) に対し，f(B₁) + … + f(B_m) を，この分割のスコアと呼ぶことにする．たとえば，((3), (1, 4), (1, 5)) のスコアは 3² + (1+4)² + (1+5)² = 70 である．

A の分割はちょうど 2^n-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 である．

Input

入力は複数のデータセットからなる．データセットの個数は 30 を超えない．各データセットは次の形式で表される．

n k
a1 a2 … an

n および k はいずれも整数であり，1 ≤ n ≤ 1000 および 1 ≤ k ≤ min{2^n-1, 2000} を満たす．各 a_i は数列 A の i 番目の要素となる整数であり，-10⁶ ≤ a_i ≤ 10⁶ を満たす．

入力の終わりは 2 つのゼロからなる行で表される．

Output

各データセットについて，A のすべての分割のスコアのうち k 番目に大きい値を，1 行に出力せよ．

Sample Input

5 1
3 1 4 1 5
5 6
3 1 4 1 5
14 255
2024 6 29 14 0 -17 0 2024 7 5 16 30 -19 30
0 0

Sample Output

196
100
8484005

---