CF191E Thwarting Demonstrations

伯兰德正经历着黑暗时期。由邻国资助的伯兰德反对派在首都 Bertown 组织了一场示威。情报部门得知，这些示威计划持续 $k$ 天。 幸运的是，伯兰德拥有一支特殊的警察部队，可以拯救国家。这支部队恰好有 $n$ 名士兵，编号从 $1$ 到 $n$。伯兰德的将军，亦即这支部队的指挥官，必须安排这支部队在这 $k$ 个艰难的日子里执行任务。在每一天里，将军必须派出一定数量的警员去驱散骚乱。由于部队人数众多，而将军并不聪明，他只能选择士兵编号从 $l$ 到 $r$ 的一个区间（包含两端），其中 $l$ 和 $r$ 可以任意选择。 现在将军面临两个问题。首先，他不能连续两次派遣同一个区间的队伍出去——否则士兵们会感到无聊而反叛。其次，并不是所有士兵都同样可靠。每个士兵有一个可靠度 $a_i$。队伍的可靠度是所有被派遣士兵的可靠度之和。单个士兵的可靠度有可能为负值，所以如果带上他反而会拖后腿。由于将军极其贪婪且目光短浅，他每天都会派出尚未派遣过的、可靠度最高的队伍去处置骚乱（即在所有没有被选中过的区间中，选择可靠度之和最大的区间）。 伯兰德政府希望知道，在这 $k$ 天驱散示威的队伍中，被派出队伍的最小可靠度是多少。将军自己无法完成这一困难任务。请你帮助他，不要让他在上级面前丢脸！

第一行包含两个整数 $n$ 和 $k$，表示部队的士兵数量和出动次数。 第二行包含 $n$ 个空格分隔的整数 $a_i$，表示每个士兵的可靠度。它们的绝对值均不超过 $10^{9}$。 请不要在 C++ 中使用 %lld 读写 64 位整数，建议使用 cin、cout 流或 %I64d。

输出一个整数，表示在 $k$ 天内被派出的所有队伍中，可靠度的最小值。

由 ChatGPT 5 翻译