U360718 项链

小 L 有一串 $n$ 块宝石的项链，它可以顺时针看成一个圆环，即第 $1$ 块宝石与第 $2$ 块和第 $n$ 块宝石相邻，第 $2$ 块宝石与第 $1$ 块和第 $3$ 块宝石相邻，以此类推。 但不幸的是，项链的宝石破碎了。每块宝石破碎的程度可以看作一个数值，顺时针起第 $i$ 块宝石的破碎值为 $a_i$。 小 L 认为，一串项链的不美观度为最大的两块相邻宝石的破碎值之和。 小 L 想了很久很久，今天，他决定拆下项链上的一些宝石，使得其剩下 $m$ 块宝石（剩下的宝石相对位置不能改变），请你帮他求出，新的项链的不美观度最小可以是多少。

第一行三个非负整数 $tid,n,m$，其中 $tid$ 表示测试点编号。 第二行 $n$ 个非负整数 $a_i$。

一行一个整数，即为答案。

#### 样例1解释 保留 $\{1,3,2\}$，不美观度为 $3+2=5$。 #### 样例2输入/输出 见下发文件。该样例满足测试点 $1 \sim 2$ 的约束条件。 #### 样例3输入/输出 见下发文件。该样例满足测试点 $3 \sim 4$ 的约束条件。 #### 样例4输入/输出 见下发文件。该样例满足测试点 $5 \sim 8$ 的约束条件。 #### 样例5输入/输出 见下发文件。该样例满足测试点 $16 \sim 20$ 的约束条件。 #### 评测用例规模与约定 | 测试点编号 | $n\le$ | $m$ | | -----------: | -----------: | -----------: | | $1,2$ | $20$ | $\le n$ | | $3,4$ | $200$ | $\le n$ | | $5,6,7,8$ | $2000$ | $\le n$ | | $9$ | $5 \times 10^5$ | $=2$ | | $10$ | $5 \times 10^5$ | $=3$ | | $11$ | $5 \times 10^5$ | $=n-1$ | | $12,13,14,15$ | $10^5$ | $\le n$ | | $16,17,18,19,20$ | $5 \times 10^5$ | $\le n$ | 对于所有数据，有 $2\le m \le n \le 5 \times 10^5$，$0 \le a_i\le 10^9$。