简单·梦想始发车

题目描述

“梦想始发车”即将于2016年12月30日启航！

已知：“梦想始发车”在一条地铁线路上行驶。这条地铁线路上有$n$个站，每个站都有各自的站间距。

求：这条地铁线路上所有可能的乘车方案的路程从小到大排序后的第$k$个数。

乘车方案须满足至少坐一个站，且仅能乘坐一次，到达终点站须清客。

输入

输入包含多组测试数据，以EOF结束。

每组数据第一行为2个数$n, k$，其中$n$代表站点数目，$k$代表所求所有路程从小到大排序后的第几个数；

第二行为$n-1$个数$x_{i}$，以一个空格分隔。对于第 $i$ 个数（$1 \leq i \leq n-1$），代表地铁线路上第 $i$ 个站到第 $i+1$ 个站的站间距（均为路程）。

保证$2 \leq n \leq 4000$，$1 \leq k \leq n(n-1)$，$1 \leq x_{i} \leq 10^{5}$

对于所给的数据，两端的终点站分别为第1个站和第n个站。

输出

对于每组数据，输出一行，一个整数，表示所求的路程。

输入样例

2 2
3
3 5
4 5

输出样例

3
9

样例解释

对于第一组数据，共有2种乘车方案，分别为从第1个站到第2个站，以及从第2个站到第1个站，其路程均为3，故从小到大排序后的第2个数为3；

对于第二组数据，地铁运行图如下：

乘车方案共如下6种：

1. 从站点1到站点2，路程为4；
2. 从站点1到站点3，路程为9；
3. 从站点2到站点1，路程为4；
4. 从站点2到站点3，路程为5；
5. 从站点3到站点1，路程为9；
6. 从站点3到站点2，路程为5.

得到所有可能的乘车方案的路程从小到大排序为：

4 4 5 5 9 9

故第5个数为9