#include <bits/stdc++.h>

using namespace std;

struct line{
    long long a;
    mutable long long b;
    mutable double l;
    bool p;
    line(double l) : l(l), p(true) {}
    line(long long a, long long b) : a(a), b(b), l(-1e18), p(false) {}
    long long eval(long long x) const {
        return a*x + b;
    }
    double intersection(set<line>::iterator l) const{
        if(a == l->a) return 0;
        return (double)(l->b - b)/(double)(a - l->a);
    }
    bool operator<(const line &l) const{
        if(!p && !l.p) return a < l.a;
        return this->l < l.l;
    }
};

struct CHT{
    set<line> s;
    inline bool check(set<line>::iterator l, set<line>::iterator m, set<line>::iterator r) const{
        return l->intersection(r) <= l->intersection(m);
    }
    void insert(line l){
        auto it = s.insert(l).first;
        if(it->b > l.b)
            return;
        it->b = l.b;
        if(it != s.begin() && next(it) != s.end() && check(prev(it), it, next(it))){
            s.erase(it);
            return;
        }
        while(it != s.begin() && prev(it) != s.begin() && check(prev(it, 2), prev(it), it))
            s.erase(prev(it));
        while(next(it) != s.end() && next(it, 2) != s.end() && check(it, next(it), next(it, 2)))
            s.erase(next(it));
        if(it != s.begin()) it->l = it->intersection(prev(it));
        if(next(it) != s.end()) next(it)->l = it->intersection(next(it));
    }
    long long get_max(long long x){
        if(s.empty()) return 0;
        return prev(s.lower_bound(line((double)x)))->eval(x);
    }   
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    vector<long long> v(n), ossz(n);
    for(long long &x : v)
        cin>>x;

    ossz[0] = v[0];
    for(int i = 1; i < n; i++)
        ossz[i] = ossz[i-1] + v[i];

    vector<long long> dp(n);
    for(int i = 0; i < n; i++)
        dp[i] = ossz[i]*abs(v[i]);
    
    for(int i = 1; i < k; i++){
        CHT cht;
        vector<long long> dp1(n);
        for(int j = i; j < n; j++){
            cht.insert(line(-ossz[j-1], dp[j-1]));
            dp1[j] = cht.get_max(abs(v[j])) + ossz[j]*abs(v[j]);
        }
        swap(dp, dp1);
    }

    cout<<dp[n-1]<<'\n';

    return 0;
}