長さ 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 つのゼロからなる行で表される.