acm International Collegiate Programming Contest

Links

A B C D E F G H I

Problem G

数列の分割

長さ 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 である.

Input

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

n k a1 a2 an

n および k はいずれも整数であり,1 ≤ n ≤ 1000 および 1 ≤ k ≤ min{2n-1, 2000} を満たす.各 ai は数列 Ai 番目の要素となる整数であり,-106 ≤ ai ≤ 106 を満たす.

入力の終わりは 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
(End of Problem G) A B C D E F G H I