该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

项链 (necklace)

题目描述

小 L 有一串 $n$ 块宝石的项链，它可以顺时针看成一个圆环，即第1块宝石与第2块和第 $n$ 块宝石相邻，以此类推。

但不幸的是，项链的宝石破碎了。每块宝石破碎的程度可以看作一个数值，顺时针起第 $i$ 块宝石的破碎值为 $a_{i}$。

小 L 认为，一串项链的不美观度为最大的两块相邻宝石的破碎值之和。

小 L 决定拆下项链上的一些宝石，使得其剩下 $m$ 块宝石（剩下的宝石相对位置不能改变），请你帮他求出，新的项链的不美观度最小可以是多少。

输入格式

在文件 necklace.in 中读入。 第一行三个非负整数 $tid$ , $n$ , $m$，其中 $tid$ 表示测试点编号。 第二行 $n$ 个非负整数 $a_{i}$。

输出格式

在文件 necklace.out 中输出。 一行一个整数，即为答案。

样例

输入数据1

0 5 3
1 4 6 3 2

输出数据1

5

提示

数据范围与提示

样例 1 解释： 保留破碎值为 $1,3,2$ 的三块宝石，相邻两块宝石的破碎值之和分别为 $1+3=4$ 与 $3+2=5$，不美观度为 $5$。

数据范围

对于所有数据，$2 \le m \le n \le 5 \times 10^{5}$，$0 \le a_{i} \le 10^{9}$。共20个测试点，每个测试点分值相等。