#H1081. G. ‘Riliane Lucifen d’Autriche’ teafrogsf 和他的四面镜子

G. ‘Riliane Lucifen d’Autriche’ teafrogsf 和他的四面镜子

题目背景

巴利索尔的儿子是独生子
身为富裕家庭的后代
任谁都羡慕的美少年
但他却有些地方不对劲
不但非常喜欢玩娃娃
总是只穿女孩子的衣服
还从母亲的房间里偷出用具
偷偷地化妆
周遭的人们都疏远着这样的他
所以他不论何时
都孤单一人
[1]

题目描述

在 knb 的形而上学数据库被击毁之后,OIER[2] 小队在这个信息屏蔽密度极高的时代彻底成为了视障者。但这一刻,蛙终于揭露了他四面镜子的真正力量:他的四面镜子中居然蕴含了 Ackermann(4,4)Ackermann(4,4) 个可以存储单位信息的结点,且它们之间均互相链接。而 knb 数据库的全部信息也被存储在他的镜子里。尽管这面镜子已经失去了它曾经的力量,没有了穿梭在其中的寄生之魂用于分析和处理信息[3],但现在他们已经看到了撬动败局的希望。

在众人的不懈努力下,他们找到了 nn 个相对重要的结点,它们的价值程度分别是 valival_i。他们打算在其中选择 mm 个结点,而通过拼接它们便能够获得有效信息,信息的价值是这mm个结点的价值之和。

由于每份信息都是独一无二的,他们打算先获得前 kk 个最重要的信息。作为 knb 和蛙共同开发(knb 负责开发,蛙负责提出 feature)的新智能,你必须计算出这 kk 个方案中价值最小的信息的价值。

数据格式与约定

输入

输入第一行包含三个正整数 n,m,k(1mn106,1k106)n,m,k(1 \le m\le n \le 10^6,1\le k\le 10^6),分别表示找到的结点,需要选择的结点个数,需要获得的信息个数。

接下来一行包含 nn 个整数 val1,val2,,valn(i,1vali109)val_1,val_2,\dots,val_n(\forall i, 1 \le val_i \le 10^9),表示每个结点的价值。

输出

输出包含一行一个整数 ansans,即价值最小的信息的价值。如果有多种选择信息的方案,任选一种即可。

如果 kk 比所有信息的数量都要大,输出 1-1

样例

3 2 2
1 2 3
4

样例解释

OIER 小队选取的两个方案按价值从小到大排序分别为:结点 11 和结点 33,价值为 44;结点 22 和结点 33,价值为 55

后记

“呼......总算搞定了。”

“好耶!”

OIER 小队的所有人都舒了一口气。数据库的恢复让他们燃起了最后的希望。

“这镜子恁牛啊。诶蛙你不是说过像这样的镜子一样的物件一共有七件吗?你咋只拿到了一件捏?”

“那都是人家的,能送我一件已经不错了,感觉这次纯属脸比较好。但是如果我们还想真正翻盘的话——”

“——就得看你的了,M晓。”


  1. 摘自 mothy 歌曲《バリーゾールの子供は一人っ子》。 ↩︎

  2. 全名为 Original Isotopy Exuviae Reconstruction。 ↩︎

  3. 详见 Evillious 系列。 ↩︎