#21 「 第K小子集和 」

统计

R君得到了一个集合,里面一共有n个正整数。

R君对这个集合很感兴趣。

R君通过努力钻研,发现了这个集合一共有$2^n$个子集。

现在R君又对这个集合的子集很感兴趣。

定义一个集合的权值是这个集合内所有数字的和的话。

那么R君想问问你,这个集合的权值第K小子集是多大。

ps.涉及到较少数字的long long输入输出,建议使用cin/cout。

输入格式

第一行两个正整数n,k。

接下来一行n个正整数,表示集合内元素。

输出格式

输出一个数字,表示集合的权值第K小子集的权值。

样例数据

input

2 3
1 2

output

2

数据规模与约定

$1 \le n \le 35$, $1 \le k \le 2^n$,$1 \le $ 集合元素$ \le 10^9$。

时间限制:1s

空间限制:512MB

Author: zrt