首先贪心策略显然，每次连边一定连相邻两个基站。不难验证代价对于 $k$ 是凸性的。

所以 wqs 二分，不考虑线路限制时是一个链上最小独立集问题（也就是相邻的不选），dp 方程不难推。

然后对代价偏移量 $c$ 做二分，表示每一个价值改成相邻距离加 $c$ 之后的链上最小独立集是多少。虽然本题要的是最小，但是实际上做出来的思路其实是类似于求最大值的。因为我们偏移量如果是 0 的话，显然是贪心策略是一个线都不连，这就和题目相悖了。所以我们的偏移量是下界负数上界 0 这样做，这个时候最优选择数量显然是随着 $c$ 递增而递减。那么类似 lower_bound 搜索，找到最小的让划分段数 $\le k$ 的 $c$ 即可。由于 $c=0$ 时划分段数是 $0$ ，所以找到的这个解一定就是恰好取 $k$ 的情况。

最终答案就是偏移 $c$ 的情况得到的最小独立集再减去 $kc$ （$k$ 是负数）。

const int N = 100010;
const i64 INF = 1145141919810ll;
struct dp_info
{
    i64 val, seg;
    dp_info(i64 d = INF, i64 s = 0) : val(d), seg(s) {}
    bool operator==(const dp_info& o) const { return (val == o.val) && (seg == o.seg); }
    bool operator>(const dp_info& o) const { return (val < o.val) || ((val == o.val) && (seg < o.seg)); }
    bool operator<(const dp_info& o) const { return !(((*this) == o) || ((*this) > o)); }
};
int n, k;
i64 d[N], a[N];
dp_info f[N][2];
dp_info solve(i64 c)
{
    f[0][0] = dp_info(0, 0), f[0][1] = dp_info();
    for (int i = 1; i <= n; ++i)
        f[i][0] = std::max(f[i - 1][0], f[i - 1][1]), f[i][1] = dp_info(f[i - 1][0].val + a[i] + c, f[i - 1][0].seg + 1);
    dp_info ret = std::max(f[n][0], f[n][1]);
    return ret;
}
int main()
{
    n = rd() - 1, k = rd();
    for (int i = 0; i <= n; ++i)
        d[i] = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = d[i] - d[i - 1];
    i64 lo = -1145141919, hi = 0;
    while (lo < hi)
    {
        i64 mi = (lo + hi) >> 1;
        bool flag = (mi == -2);
        (solve(mi).seg > k) ? (lo = mi + 1) : (hi = mi);
    }
    wr(solve(lo).val - (lo) * k);
}