#include <stdlib.h>

// 演算法 / Algorithm:
// 固定左端 l 時，v(l,r)=max-min 隨 r 增大而不減 → 每個 l 的最大值在 r=n-1。
// For fixed l, v(l,r) is non-decreasing in r, so its max is at r=n-1.
// 用最大堆裝每個 l 的 v(l,n-1)，彈 k 次堆頂；彈出 (l,r) 後若 r>l 推入 (l,r-1)。
// Seed a max-heap with v(l,n-1) per l; pop k times, after popping (l,r) push (l,r-1).
// 稀疏表讓區間 max/min 查詢變 O(1) / Sparse tables make range max/min O(1).

static int LOG[50005];            // LOG[x] = floor(log2(x))，查詢時用 / used to pick the right table level

// 堆的節點：價值、左端、右端 / heap node: value, left index, right index
typedef struct { int val; int l; int r; } Node;

static Node *heap;                // 堆的陣列 / array backing the heap
static int heapSize;              // 目前堆裡的元素個數 / current number of elements

// 把節點推入最大堆，並向上調整 / push a node and sift it up to keep max-heap order
static void hpush(Node x) {
    int i = heapSize++;           // 放在末端，i 為新位置 / place at the end
    heap[i] = x;
    while (i > 0) {               // 與父節點比較，比父大就上浮 / bubble up while bigger than parent
        int p = (i - 1) / 2;      // 父節點索引 / parent index in a 0-based binary heap
        if (heap[p].val >= heap[i].val) break;  // 父已不小，停止 / parent not smaller → done
        Node t = heap[p]; heap[p] = heap[i]; heap[i] = t;  // 交換 / swap with parent
        i = p;
    }
}

// 彈出並回傳堆頂（最大值），再向下調整 / pop the max (root) and sift down to restore order
static Node hpop(void) {
    Node top = heap[0];           // 堆頂就是最大值 / root holds the maximum
    heap[0] = heap[--heapSize];   // 把最後一個搬到頂端 / move last element to the root
    int i = 0;
    while (1) {
        int l = 2 * i + 1, r = 2 * i + 2, m = i;  // 左右子節點索引 / children indices
        if (l < heapSize && heap[l].val > heap[m].val) m = l;  // 找較大的子節點 / pick larger child
        if (r < heapSize && heap[r].val > heap[m].val) m = r;
        if (m == i) break;        // 已經比兩個子節點大，停止 / heap property restored
        Node t = heap[m]; heap[m] = heap[i]; heap[i] = t;      // 與較大子節點交換 / swap down
        i = m;
    }
    return top;
}

// 用稀疏表 O(1) 算 v(l,r)=max-min / compute v(l,r)=max-min in O(1) via sparse tables
// mx/mn 是攤平的二維表，索引方式 mx[level*n + i] / mx,mn are flat 2D tables: mx[level*n + i]
static int rangeVal(int *mx, int *mn, int n, int l, int r) {
    int j = LOG[r - l + 1];                  // 選最大的 2^j <= 區間長度 / largest power-of-two ≤ length
    int span = 1 << j;                       // 2^j，位移即乘法 / 1<<j means 2^j
    // 兩段長度 2^j 的區間覆蓋 [l,r]（可重疊）/ two length-2^j windows cover [l,r] (overlap is fine for max/min)
    int hiA = mx[j * n + l], hiB = mx[j * n + (r - span + 1)];
    int hi = hiA > hiB ? hiA : hiB;          // 區間最大 / range maximum
    int loA = mn[j * n + l], loB = mn[j * n + (r - span + 1)];
    int lo = loA < loB ? loA : loB;          // 區間最小 / range minimum
    return hi - lo;                          // 價值 = 最大 - 最小 / value = max - min
}

long long maxTotalValue(int* nums, int numsSize, int k) {
    int n = numsSize;

    // 預計算 LOG 表 / precompute floor-log2 for query speed
    LOG[1] = 0;
    for (int i = 2; i <= n; i++) LOG[i] = LOG[i / 2] + 1;
    int K = LOG[n] + 1;                       // 稀疏表的層數 / number of levels needed

    // 配置兩張稀疏表（攤平）/ allocate the two sparse tables (flattened)
    int *mx = (int*)malloc((size_t)K * n * sizeof(int));  // malloc 動態配記憶體 / dynamic allocation
    int *mn = (int*)malloc((size_t)K * n * sizeof(int));
    for (int i = 0; i < n; i++) { mx[i] = nums[i]; mn[i] = nums[i]; }  // 第 0 層 = 單一元素 / level 0 = single elements

    // 用上一層拼出這一層 / build each level from the previous one
    for (int j = 1; j < K; j++) {
        int half = 1 << (j - 1);              // 上一層區間長度 / previous level's window length
        for (int i = 0; i + (1 << j) <= n; i++) {
            int a = (j - 1) * n + i;          // 左半段 / left half starting at i
            int b = (j - 1) * n + i + half;   // 右半段 / right half starting at i+half
            mx[j * n + i] = mx[a] > mx[b] ? mx[a] : mx[b];  // 合併取大 / combine by taking max
            mn[j * n + i] = mn[a] < mn[b] ? mn[a] : mn[b];  // 合併取小 / combine by taking min
        }
    }

    // 堆最多同時放 n 個（每個 l 一個）/ heap holds at most n nodes (one per left endpoint l)
    heap = (Node*)malloc((size_t)n * sizeof(Node));
    heapSize = 0;
    for (int l = 0; l < n; l++) {             // 放入每條鏈的頭 v(l,n-1) / seed each chain's head
        Node x = { rangeVal(mx, mn, n, l, n - 1), l, n - 1 };
        hpush(x);
    }

    long long ans = 0;                        // 答案可達 1e5*1e9=1e14，必須用 long long / sum can reach 1e14
    for (int t = 0; t < k; t++) {             // 取最大的 k 個價值 / take the k largest values
        Node top = hpop();                    // 目前所有未取值中的最大 / global current maximum
        ans += top.val;
        if (top.r > top.l) {                  // 同一條鏈還有下一個 / chain still has a next element
            Node nx = { rangeVal(mx, mn, n, top.l, top.r - 1), top.l, top.r - 1 };
            hpush(nx);                        // 推入 v(l,r-1) / push the next (smaller) value of this chain
        }
    }

    free(mx); free(mn); free(heap);           // 釋放記憶體，避免洩漏 / free to avoid memory leaks
    return ans;
}