マシンは \(A_i\) は降順にソートされているとしてよいです。 このとき、マシン 1 から始めて 1,2 を交互に使うのが最適になります。

証明：
同じマシンを連続して選べないことから、マシン 1 を選べる回数は高々 \(\left\lceil\frac{K}{2}\right\rceil\) 回であり、少なくとも \(K-\left\lceil\frac{K}{2}\right\rceil\) 回はマシン 2 以降を選ぶ必要があります。よって、効果の合計は \(A_1\left\lceil\frac{K}{2}\right\rceil+A_2\left(K-\left\lceil\frac{K}{2}\right\rceil\right)\) 以下になります。一方「マシン 1 から始めて 1,2 を交互に使う」ことでこの値を達成できます。

以上から、 \(A\) を降順ソートし、 \(A_1\left\lceil\frac{K}{2}\right\rceil+A_2\left(K-\left\lceil\frac{K}{2}\right\rceil\right)\) が答えとなります。以下の実装例では、この式を変形し \(A_1\left(K-\left\lfloor\frac{K}{2}\right\rfloor\right)+A_2\left\lfloor\frac{K}{2}\right\rfloor\) として計算しています。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a.rbegin(), a.rend());
  cout << (long long)a[0] * (k-k/2) + (long long)a[1] * (k/2) << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(A[0] * (K-K//2) + A[1] * (K//2))