小 R 的长跑训练被划分为连续的 n 个路段，第 i 个路段的长度为正整数 a_i。

一次连续训练可以从任意路段开始，在其后的任意路段结束，但中途不能跳过路段。也就是说，每个满足 1\le l\le r\le n 的区间 [l,r] 都对应一次连续训练，其里程为

a_l+a_{l+1}+\cdots+a_r.

一共有 \frac{n(n+1)}2 个连续区间。把它们的里程从小到大排列，相同的里程需要重复计算。

教练想选取其中第 k 小的里程作为训练参考值。请你求出这个值。

第一行输入两个整数 n,k。

第二行输入 n 个整数 a_1,a_2,\ldots,a_n，表示各路段长度。

输出一行一个整数，表示所有连续区间里程中的第 k 小值。

样例说明 1

长度为 1 的区间里程为 2,1,3,2,4；长度为 2 的区间里程为 3,4,5,6。

所有区间里程排序后，前七个依次为

1,2,2,3,3,4,4.

因此第 7 小的里程为 4。两个值为 4 的区间要分别计算。

样例说明 2

本组数据包含多个相同的区间和，用于提醒你正确处理重复值。

数据范围

对于所有测试数据，保证：

• 1\le n\le10^5；
• 1\le a_i\le10^5；
• 1\le k\le\frac{n(n+1)}2；
• 输入的所有数均为整数。

本题共 10 个测试点，每个测试点 10 分。

特殊性质 A：k=1。

特殊性质 B：a_1=a_2=\cdots=a_n。

月赛二分答案26年8月