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

题目背景

魔法阵的激活不仅需要强大的初始能量，还需要在终结时释放出强大的能量波动。作为守护者，你需要巧妙地选择初始激活的魔法石，以最大化总成本，从而确保魔法阵能够抵御最强大的黑暗力量。

题目描述

在古老的魔法王国中，有一座由 n 块魔法石组成的魔法阵，每块魔法石都蕴含着不同的能量值 (ai)。初始时，所有魔法石都散发着红色的光芒，象征着未被激活的状态。

作为魔法阵的守护者，你需要激活这些魔法石以启动魔法阵的防御系统。激活规则如下：

• 初始激活：你必须选择恰好 k 块魔法石，并将它们涂为蓝色，表示激活。这些魔法石的能量值之和将作为初始激活成本的一部分。
• 连锁反应：在至少还有一块红色魔法石的情况下，你可以反复选择任意一块与蓝色魔法石相邻的红色魔法石，并将其涂为蓝色。这一过程会持续到所有魔法石都被激活。
• 终结仪式：最后一个被涂为蓝色的魔法石的能量值将作为终结成本的一部分。

总成本定义为初始激活成本与终结成本之和。你的任务是设计一种激活策略，使得给定魔法阵可能达到的总成本最大。

输入描述

第一行包含两个整数 n（2≤n≤5000） 和 k（1≤k＜n），分别表示魔法石的数量和初始激活的魔法石数量。

第二行包含 n 个整数 a1 a2 … an，表示每块魔法石的能量值。1≤ai≤10^9。

输出描述

输出一个整数，表示可能达到的最大总成本。

样例输入

输入1：

5 2
3 1 5 2 4

输入2：

3 1
1 2 3

样例输出

输出1：

12

输出2：

5

样例解释

样例1解释：

初始选择能量值为 5 和 4 的魔法石（初始成本为 5 + 4 = 9），然后按照顺序激活相邻的魔法石，最后一个被激活的是能量值为 3 的魔法石（终结成本为 3），总成本为 9 + 3 = 12。

样例2解释：

初始选择能量值为 2 的魔法石（初始成本为 2），然后按照1、3顺序激活相邻的魔法石，最后一个被激活的是能量值为 3 的魔法石（终结成本为 3），总成本为 2 + 3 = 5。

数据范围

数据范围见题目描述。