← 返回题目列表

Codeforces · 191/E

E. 阻挠示威

中文机器翻译题面 查看原题

现在是 Berland 的黑暗时期。贝尔兰反对派在邻国的资助下,在贝尔兰首府贝尔敦组织了示威活动。通过情报工作我们知道示威活动计划持续k天。

幸运的是,贝兰德有一支特警部队,可以拯救国家。它有n个士兵,编号从1到n。贝尔兰德将军,作为支队的指挥官,必须安排好支队在这艰难的k天内的工作。在这些日子里,将军必须派出一定数量的警察去驱散骚乱。由于支队规模较大,将军又不太聪明,只能选择编号为l到r(含)的所有士兵的集合,其中l和r是任意选择的。

现在将军有两个问题。首先,他不能两次派出同一支部队——士兵们会感到无聊,然后叛变。其次,并非所有士兵都同样可靠。每个士兵都有人工智能的可靠性。支队的可靠性是指该支队士兵的可靠性之和。单个士兵的可靠性可能是负面的,那么当你把他纳入分队时,他只会破坏事情。这位将军以贪婪和短视着称,因此每天他都会派出最可靠的士兵队伍(即所有尚未派遣的士兵队伍中)去解散。

Berland 政府已决定了解在这 k 天内派去驱散示威活动的分遣队的最低可靠性。将军本人无法应付如此艰巨的任务。帮助他不要在上级面前丢脸!

输入

第一行包含两个整数 n 和 k $$( 1 \leqslant n \leqslant 1 0 ^ { 5 }, 1 \leqslant k \leqslant \frac { n ( n + 1 ) } { 2 } )$$ — 分队中的士兵人数和某人执行任务的次数。

第二行包含n个空格分隔的整数ai,它们的绝对值不超过109——士兵的可靠性。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数,最好使用 %I64d 说明符的 cin、cout 流。

输出

打印一个数字 — 在这 k 天内值班的小组所寻求的最低可靠性。

示例

输入 #1

3 4
1 4 2

输出 #1

4

输入 #2

4 6
2 -1 2 -1

输出 #2

1

输入 #3

8 10
1 -2 3 -4 5 -6 7 -8

输出 #3

2