UOJ Logo LFYZ Online Judge

LFYZOJ

#29. 穰子的雪糕

统计

问题描述

一天,poorpool 在幻想乡内的化身秋穰子买了雀巢 8 次方雪糕(这是一种有 8 个排列成一长条格子,每个格子里放着一块巧克力雪糕的雪糕)。她觉得十分好吃 。

穰子是爱好学习的女孩子,因此,她推广到了雀巢 $n$ 次方雪糕,她还有一个问题要问你呢:

给你一个长度为 $n$ 的序列,请你告诉穰子,这个序列里的第 $k$ 大的连续区间和是多少?

比如说,有一个长度为 4 的区间是1 2 4 3 ,它里头有 $1+2+3+4=10$ 个连续区间,分别是1,2,3,4,1 2,2 4,4 3,1 2 4,2 4 3,1 2 4 3。每个区间的(排了序的)和是 10 9 7 7 6 4 3 3 2 1,其中第 1 大的是10,第 3 大的是7,第 4 大的也是7,第 10 大的是1

输入格式

第一行两个整数 $n,k$。 第二行 $n$ 个整数,第 $i$ 个是序列中的第 $i$ 个数。

输出格式

一个整数,是这个序列里的第 $k$ 大的连续区间和。

样例一

input

4 5
1 2 4 3

output

6

数据范围与约定

对于 $60\%$ 的数据,$n \leq 300$。

对于 $100\%$ 的数据,$n \leq 300000$,$k \leq \frac{n(n+1)}{2}$,序列中的数都 $\leq 1000$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$