#P4504. K个串

    ID: 3741 传统题 1000ms 512MiB 尝试: 684 已通过: 170 难度: 8 上传者: 标签>CF2400提高+/省选-可持久化线段树懒标记线段树路径复制最佳优先搜索二叉堆离散化

K个串

题目描述

兔子们在玩 kk 个串的游戏。首先,它们拿出了一个长度为 nn 的数字序列,选出其中的一个连续子串,然后统计其子串中所有数字之和(注意这里重复出现的数字只被统计一次)。

兔子们想知道,在这个数字序列所有连续的子串中,按照以上方式统计其所有数字之和,第 kk 大的和是多少。

输入格式

第一行,两个整数 nn 和 kk,分别表示长度为 nn 的数字序列和想要统计的第 kk 大的和。

接下来一行 nn 个数 aia_i,表示这个数字序列。

输出格式

一行一个整数,表示第 kk 大的和。

样例输入

7 5
3 -2 1 2 2 1 3

样例输出

4

数据规模与约定

1≤n≤1051 \le n \le 10^5,1≤k≤2×1051 \le k \le 2\times10^5,0≤∣ai∣≤1090 \le |a_i| \le 10^9。

数据保证存在第 kk 大的和。