Problem1524--子序列问题Ⅳ

1524: 子序列问题Ⅳ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 86  Solved: 34
[Submit] [Status] [Web Board] [Creator:]

Description

给定含有n个数字的序列,你可以从中选出任意一个子序列。
设子序列的和为sum,请问所有情况中第k小的sum是多少?

Input

第一行输入两个正整数n,k,其中有:n<=10^5,k<=2*10^5。保证数据合法。
第二行n个正整数,第i个数为ai,ai<=10^9。

Output

输出所有情况中第k小的sum。

Sample Input

3 5
1 2 3

Sample Output

4

HINT

样例解释:
对于序列{1,2,3},其含有7种不同的子序列选法:{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3},对应的sum分别是1,2,3,3,4,5,6。
因此第5小的sum值为4。

Source/Category