#includebitsstdc++husing namespace std;const int N = 2e5+10;#define repilr forint i = l;i = r;i++#define ll long long#define db doublell nmdpNhNcnN;stackllq1;struct node ll bx;; node ckll t返回b与x

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define rep(i,l,r) for(int i = l;i <= r;i++)
#define ll long long
//#define db double

ll n,m,dp[N],h[N],cn[N];
stack<ll>q1;

struct node{
    ll b,x;
};

// 计算在给定的 t 值下，最小的代价以及需要改变的次数
node ck(ll t){
    while(!q1.empty()) q1.pop();
    q1.push(1);
    rep(i,2,n){
        dp[i] = dp[i-1] + abs(h[i]-h[i-1]);
        cn[i] = cn[i-1];
        while(!q1.empty()){
            ll k1 = dp[q1.top()] + abs(h[q1.top()]-h[i]) - t;
            if(k1 == dp[i]){
                cn[i] = min(cn[i], cn[q1.top()]+1);
            }
            if(k1 < dp[i]){
                dp[i] = k1;
                cn[i] = cn[q1.top()] + 1;
            }
            if(h[q1.top()] >= h[i]){
                break;
            }
            q1.pop();
        }
        q1.push(i);
    }
    return {dp[n], cn[n]};
}

// 二分法确定最小的 t 值
void erfen(ll l,ll r,ll x){
    while(l < r){
        ll mid = l + (r-l+1)/2 - 1;
        if(ck(mid).x >= x){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    cout << r*x + ck(r).b << '\n'; // 此时 r 为 k
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    rep(i,1,n) cin >> h[i];

    if(ck(0).x <= m){
        cout << ck(0).b << '\n'; // k 为 0
    }
    else{
        erfen(-1e16, 1e16, m);
    }
    return 0;
}
``