問題文

NN 個の整数 A1,...,ANA_1, ..., A_N があります。

このうち 00 個以上を選んで組とする方法は 2N2^N 通りありますが、そのそれぞれについてそれらの和を求め、 小さい順に並べ替えたとき、 KK 番目にくる数は何になるでしょう?

制約

  • 1N341 \leq N \leq 34
  • 1Ai1091 \leq A_i \leq 10^9
  • 1Kmin(2N,109)1 \leq K \leq \min(2^N, 10^9)

入力

入力はすべて整数である。

N K
A_1 A_2 ... A_N

出力

計算結果を一行に出力せよ。

サンプル

入力1
3 4
1 2 3
出力1
3

和を小さい順に並べると 0, 1, 2, 3, 3, 4, 5, 60,\ 1,\ 2,\ 3,\ 3,\ 4,\ 5,\ 6 となります。

入力2
5 32
1000000000 1000000000 1000000000 1000000000 1000000000
出力2
5000000000

オーバーフローに注意してください。

提出


Go (1.21)