U621016 k strings

拼尽全力无法战胜！

给定正整数 $n$，正整数 $k$，以及长度为 $n$ 的整数序列： $$a=a_1,a_2,\cdots, a_n(a_i\in \Z)$$ 对于每一对下标 $1\le l\le r\le n$，定义区间 $[l,r]$ 的**去重和**： $$S(l,r)=\sum_{x\in \operatorname{set}\{a_l,a_{l+1},\cdots,a_r\}} x$$ 其中，$\operatorname{set}$ 表示该区间内不同值的集合（即重复的值在求和时只计一次）。 将所有可能的区间去重和看成一个多重集合： $$S'=\{S(l,r)\mid1\le l\le r\le n\}$$ 元素个数为 $|S'|=\frac{n(n+1)}{2}$（相同的和按出现次数重复计入）。 令 $b_1\ge b_2\ge \cdots\ge b_{\frac{n(n+1)}{2}}$ 为按非增序排列的 $S'$ 中元素（允许相同值多次出现）。目标为求 $b_k$，即**第 $k$ 大去重和**。

第一行两个整数 $n$ 和 $k$。 第二行 $n$ 个整数 $a_i$。

第一行输出一个答案，即第 $k$ 大的去重和。

对于 $20\% $的数据，$1 \le n \le 2000$。 对于另外 $20\%$ 的数据，$0 \le a_i \le 10^9$。 对于 $100\%$ 的数据，$1 \le n \le 100000$, $1 \le k \le 200000$, $0 \le |a_i| \le 10^9$。 数据保证存在第 $k$ 大的和