CF191E.Thwarting Demonstrations

It is dark times in Berland. Berlyand opposition, funded from a neighboring state, has organized a demonstration in Berland capital Bertown. Through the work of intelligence we know that the demonstrations are planned to last for k days.

Fortunately, Berland has a special police unit, which can save the country. It has exactly n soldiers numbered from 1 to n. Berland general, the commander of the detachment, must schedule the detachment's work in these difficult k days. In each of these days, the general must send a certain number of police officers to disperse riots. Since the detachment is large and the general is not very smart, he can only select a set of all soldiers numbered from l to r, inclusive, where l and r are selected arbitrarily.

Now the general has exactly two problems. First, he cannot send the same group twice — then soldiers get bored and they rebel. Second, not all soldiers are equally reliable. Every soldier has a reliability of a__i. The reliability of the detachment is counted as the sum of reliabilities of soldiers in it. The reliability of a single soldier can be negative, then when you include him in the detachment, he will only spoil things. The general is distinguished by his great greed and shortsightedness, so each day he sends to the dissolution the most reliable group of soldiers possible (that is, of all the groups that have not been sent yet).

The Berland Government has decided to know what would be the minimum reliability of the detachment, sent to disperse the demonstrations during these k days. The general himself can not cope with such a difficult task. Help him to not embarrass himself in front of his superiors!

伯兰德正处在一个黑暗时期。邻国资助的伯兰德反对派在伯兰德首都贝尔托恩组织了一场示威活动。通过情报工作，我们得知此次示威将持续 $k$ 天。

幸运的是，伯兰德拥有一支特殊的警察部队，可以拯救国家。该部队恰好有 $n$ 名士兵，编号从 $1$ 到 $n$。伯兰德将军——该部队的指挥官——必须为这艰难的 $k$ 天安排部队执勤任务。在这 $k$ 天中的每一天，将军都必须派出一定数量的警员去驱散骚乱。由于部队规模庞大，而将军又不太聪明，他每次只能选择一个连续编号的士兵子集，即所有编号在 $l$ 到 $r$（含端点）之间的士兵，其中 $l$ 和 $r$ 可任意选定。

目前，将军面临两个问题。第一，他不能两次派出完全相同的士兵组合——否则士兵会感到厌烦并发动叛乱。第二，并非所有士兵的可靠性都相同。每名士兵 $i$ 具有可靠性 $a_i$。部队的可靠性定义为其中所有士兵可靠性之和。单个士兵的可靠性可能为负数；若将其编入部队，反而会降低整体可靠性。而这位将军以极度贪婪与目光短浅著称，因此每天他都会派出尚未使用过的、可靠性最高的士兵组合（即在所有尚未派出的连续子数组中，选择可靠性总和最大的那个）。

伯兰德政府希望知道：在这 $k$ 天内，被派去驱散示威活动的部队中，可靠性最小值是多少？将军本人无法完成如此艰巨的任务。请帮助他，以免他在上级面前出丑！

The first line contains two integers n and k — the number of soldiers in the detachment and the number of times somebody goes on duty.

The second line contains n space-separated integers a__i, their absolute value doesn't exceed 109 — the soldiers' reliabilities.

Please do not use the %lld specifier to read or write 64-bit integers in С++, it is preferred to use cin, cout streams of the %I64d specifier.

第一行包含两个整数 $n$ 和 $k$ —— 分别表示该小队中士兵的人数以及值班的总次数。

第二行包含 $n$ 个以空格分隔的整数 $a_i$，其绝对值不超过 $10^9$ —— 表示各士兵的可靠性。

在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符；推荐使用 cin / cout 流或 %I64d 说明符。

Print a single number — the sought minimum reliability of the groups that go on duty during these k days.

输出一个整数——即这 k 天中执行任务的各组的最小可靠性值。