金融管理

题目描述

你是一家顶尖投资银行的金融工程师. 银行拥有一个包含 $n$ 个投资项目的资产池，第 $i$ 个项目的预期收益用一个整数 $a_i$ 表示(正数表示收益，负数表示亏损). 客户提出一个特殊需求：

在所有可能的投资组合中，请求出收益总和第 $k$ 大的收益.

即，在 $a_i$ 的所有子序列中，求出第 $k$ 大子序列和.

子序列是一个可以由整个序列删除某些或不删除元素派生而来的数组，且派生过程不改变剩余元素的顺序. 特别地，空序列的和视为 $0$.

输入

共 $2$ 行，第 $1$ 行包含 $2$ 个整数 $n, k$，第 $2$ 行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个项目的预期收益.

输出

一个整数，表示第 $k$ 大子序列和.

数据范围

$1 \le n \le 10^6$

$1 \le k \le \min(10^4, 2^n)$

$-10^9 \le a_i \le 10^9$

输入输出样例

输入1：

3 5
2 4 -2

输出1：

2

解释： 所有可能获得的子序列和列出如下，按递减顺序排列：$6, 4, 4, 2, 2, 0, 0, -2$ 数组的第 $5$ 大和是 $2$ 。

输入2

6 16
1 -2 3 4 -10 12

输出2：

10