You are given a sorted array $a_1, a_2, \dots, a_n$ (for each index $i > 1$ condition $a_i \ge a_{i-1}$ holds) and an integer $k$.

You are asked to divide this array into $k$ non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. 

Let $max(i)$ be equal to the maximum in the $i$-th subarray, and $min(i)$ be equal to the minimum in the $i$-th subarray. The cost of division is equal to $\sum\limits_{i=1}^{k} (max(i) - min(i))$. For example, if $a = [2, 4, 5, 5, 8, 11, 19]$ and we divide it into $3$ subarrays in the following way: $[2, 4], [5, 5], [8, 11, 19]$, then the cost of division is equal to $(4 - 2) + (5 - 5) + (19 - 8) = 13$.

Calculate the minimum cost you can obtain by dividing the array $a$ into $k$ non-empty consecutive subarrays. 


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($ 1 \le a_i \le 10^9$, $a_i \ge a_{i-1}$). 


-----Output-----

Print the minimum cost you can obtain by dividing the array $a$ into $k$ nonempty consecutive subarrays. 


-----Examples-----
Input
6 3
4 8 15 16 23 42

Output
12

Input
4 4
1 3 3 7

Output
0

Input
8 1
1 1 2 3 5 8 13 21

Output
20



-----Note-----

In the first test we can divide array $a$ in the following way: $[4, 8, 15, 16], [23], [42]$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n, k = getList()
nums = getList()

diff = []

for i, j in zip(nums, nums[1:]):
    diff.append(j - i)

diff.sort()
print(sum(diff[:(n-k)]))

n, k = list(map(int, input().split()))
arr = [int(x) for x in input().split()]
diff = [0] * (n - 1)
p = arr[-1] - arr[0]
for i in range(n - 1):
    diff[i] = arr[i + 1] - arr[i]
diff.sort(reverse=True)
print(p - sum(diff[:k - 1]))


def __starting_point():
    s = input().rstrip().split()
    N = int(s[0])
    K = int(s[1])
    a = list(map(int, list(input().rstrip().split())))
    #Make K-1 cuts
    diff = []
    for i in range(1, N):
        diff.append([i, a[i] - a[i - 1]])
    diff = sorted(diff, key = lambda x: -x[1])
    res = max(a) - min(a)
    #k = K - 1
    #print("len diff = " + str(len(diff)))
    k = 0
    while (k < K - 1 and k < len(diff)):
        res -= diff[k][1]
        #print(res)
        k += 1
    print(res)
__starting_point()

def main():
    import sys
    input = sys.stdin.readline
    
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    kek = [0] * (n - 1)
    for i in range(n - 1):
        kek[i] =  -arr[i + 1] + arr[i]
    
    kek.sort()
    
    ans = arr[-1] - arr[0]
    for i in range(k - 1):
        ans += kek[i]
    
    print(ans)
    
    return 0

main()

n,k=list(map(int, input().split()))
a = list(map(int, input().split()))

c = a[-1] - a[0]

d = [a[i]-a[i-1] for i in range(1, n)]
d = sorted(d)[::-1]
c -= sum(d[:k-1])
print(c)



n,k = map(int,input().split())
a = list(map(int,input().split()))

if k == 1:
    print(max(a) - min(a))
    return

dif = []
for i in range(n - 1):
    dif.append(a[i + 1] - a[i])
dif = sorted(dif)
print(sum(dif[:-k + 1]))

import sys
input = sys.stdin.readline
n,k=list(map(int,input().split()))
A=[int(i) for i in input().split()]
B=[]
for i in range(1,n):
  B.append(A[i]-A[i-1])
B.sort()
print(sum(B[:n-k]))


n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = a[-1] - a[0]
delta = [-a[i] + a[i - 1] for i in range(1, n)]
delta.sort()
ans += sum(delta[:(k-1)])
print(ans)

n, k = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
k -= 1
arr_new = sorted([arr[i+1]-arr[i] for i in range(n-1)], reverse=True)
print(arr[-1]-arr[0]-sum(arr_new[:k]))


n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n - 1):
    b.append(a[i + 1] - a[i])
b.sort()
print(sum(b[:len(b) - k + 1]))

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
diff = []
if n == 1:
    print(0)
else:
    for i in range(n-1):
        diff.append(a[i+1]-a[i])

    diff.sort(reverse = True)
    ans = a[-1] - a[0]
    for i in range(min(k-1, len(diff))):
        ans -= diff[i]

    print(ans)


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))

new_arr = []
for i in range(n - 1):
	new_arr.append(arr[i + 1] - arr[i])

new_arr.sort()
print(sum(new_arr[:n - k]))


N, K = list(map(int, input().split()))
A = [int(a) for a in input().split()]
D = sorted([A[i+1]-A[i] for i in range(N-1)])
print(A[-1]-A[0]-(sum(D[-K+1:]) if K-1 else 0))


n, k = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]
span = data[-1] - data[0]
delta = [data[i+1] - data[i] for i in range(n-1)]
delta.sort(reverse=True)
print(span - sum(delta[:k-1]))



n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
t = []
for i in range(1,n):
    t.append(a[i]-a[i-1])
t.sort()
print(sum(t[:n-k]))


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = []
for q in range(n-1):
    s.append([a[q+1]-a[q], q])
s.sort(reverse=True)
d = {q[1] for q in s[:k-1]}
ans = 0
q1 = a[0]
for q in range(n-1):
    if q in d:
        ans += a[q]-q1
        q1 = a[q+1]
print(ans+a[-1]-q1)


n, k = map(int, input().split())
l = list(map(int, input().split()))
cost = l[n - 1] - l[0]
if k == 1:
	print(cost)
else:
	diff = [0 for _ in range(n - 1)]
	for i in range(n - 1):
		diff[i] = l[i + 1] - l[i]
	#print(diff)
	diff = sorted(diff)
	diff.reverse()
	print(cost - sum(diff[:k - 1]))

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(n - 1):
    B.append([A[i + 1] - A[i], i])
B.sort(reverse=True)
C = []
for i in range(k - 1):
    C.append(B[i][1])
C.sort()
ans = 0
mi = 10 ** 9
ma = -10 ** 9
u = 0
for i in range(n):
    mi = min(mi, A[i])
    ma = max(ma, A[i])
    if u < len(C) and i == C[u]:
        ans += ma - mi
        mi = 10 ** 9
        ma = -10 ** 9
        u += 1
print(ans + ma - mi)

import sys

n, k = list(map(int, sys.stdin.readline().strip().split()))
a = list(map(int, sys.stdin.readline().strip().split()))
b = [0] * (n-1)
for i in range (0, n-1):
    b[i] = a[i+1]-a[i]
b.sort(reverse = True)
print(a[n-1]-a[0]-sum(b[0:k-1]))


import sys
##a = list(map(int, sys.stdin.readline().split()))

n, k = list(map(int, sys.stdin.readline().split()))
a = list(map(int, sys.stdin.readline().split()))

d = []
for i in range(1, n):
    d.append(a[i] - a[i-1])
d.sort()
print(sum(d[:n-k]))


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
diffs = []
for i in range(1, n):
    if arr[i] != arr[i - 1]:
        diffs.append(arr[i] - arr[i - 1])
diffs = list(reversed(sorted(diffs)))

ans = sum(diffs)

# print(diffs)

for i in range(min(len(diffs), k - 1)):
    ans -= diffs[i]

print(ans)

n, k = list(map(int, input().split()))
l =  list(map(int, input().split()))
l1 = []
for i in range(n-1):
    l1.append(l[i+1]-l[i])
l1.sort()
if (k==1):
    print(sum(l1))
else:
    print(sum(l1[:-k+1]))

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
diff = []
for a1, a2 in zip(a[:], a[1:]):
    diff.append(a2 - a1)
diff.sort()
print(sum(diff) - sum(diff[::-1][:k-1]))