#include <bits/stdc++.h>

using namespace std;

int dp[101][100001];

int main()
{

    //ifstream cin("in.txt");

    int n;
    cin >> n;
    int k;
    cin >> k;

    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    vector<int> pS(n+1);
    for(int i = 1; i <= n; i++){
        pS[i] = pS[i-1] + a[i];
        //cout << pS[i] << " ";
    }
    //cout << '\n';

    /*for(int i = 1; i <= n; i++){
        dp[1][i] = pS[i] * a[i];
    }*/

    for(int i = 1; i <= k; i++){
        //cout << i <<": ";
        for(int j = i; j <= n; j++){
            int maxi = 0;
            for(int k = i-1; k <= j-1; k++){
                //cout << dp[i-1][k] + (pS[j] - pS[k]) * abs(a[j]) << " ";
                maxi = max(dp[i-1][k] + (pS[j] - pS[k]) * abs(a[j]), maxi);
            }
            dp[i][j] = maxi;

            //cout << '\n';
        }
        //cout << '\n';
    }


    cout << dp[k][n];



    return 0;
}