You are given an array $a_1, a_2, \dots, a_n$ 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 $f(i)$ be the index of subarray the $i$-th element belongs to. Subarrays are numbered from left to right and from $1$ to $k$.

Let the cost of division be equal to $\sum\limits_{i=1}^{n} (a_i \cdot f(i))$. For example, if $a = [1, -2, -3, 4, -5, 6, -7]$ and we divide it into $3$ subbarays in the following way: $[1, -2, -3], [4, -5], [6, -7]$, then the cost of division is equal to $1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9$.

Calculate the maximum 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$ ($ |a_i| \le 10^6$). 


-----Output-----

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


-----Examples-----
Input
5 2
-1 -2 5 -4 8

Output
15

Input
7 6
-3 0 -1 -2 -2 -4 -1

Output
-45

Input
4 1
3 -1 6 0

Output
8

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
a    = list(map(int, input().split()))
a    = a[::-1]
s    = [a[0]]
S    = 0

for x in a[1:]:
    s.append(s[-1]+x)

S   += s[-1]
s.pop()
k   -= 1
s   = sorted(s)

i=0
while i<=k-1:
    S += s.pop()
    i += 1
print(S)    

N, K = list(map(int, input().split()))
A = [int(a) for a in input().split()]
B = [0] * N
B[N-1] = A[N-1]
for i in range(N-1)[::-1]:
    B[i] = B[i+1] + A[i]

print(sum(sorted(B[1:])[::-1][:K-1])+B[0])


n, k = map(int, input().split())
mass = [int(i) for i in input().split()]
mass = mass[::-1]
summ = 0
m = []
for i in range(n - 1):
    summ += mass[i]
    m.append(summ)
m = sorted(m, reverse = True)
print(sum(mass) + sum(m[:k - 1]))


def main():
    buf = input()
    buflist = buf.split()
    n = int(buflist[0])
    k = int(buflist[1])
    buf = input()
    buflist = buf.split()
    a = list(map(int, buflist))
    a_sum = []
    for i in range(1, len(a)+1):
        if not a_sum:
            a_sum.append(a[-i])
        else:
            a_sum.append(a[-i]+a_sum[-1])
    cost = a_sum.pop()
    a_sum.sort(reverse=True)
    for i in range(k-1):
        cost += a_sum[i]
    print(cost)

def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline

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

SUM=[0]
for a in A[::-1]:
    SUM.append(SUM[-1]+a)

SUM=SUM[::-1]
#print(SUM)

ANS=SUM[0]
ANS+=sum(sorted(SUM[1:-1],reverse=True)[:k-1])
print(ANS)



def gns():
    return list(map(int,input().split()))
n,k=gns()
ns=gns()
sm=[ns[-1]]
for i in reversed(list(range(n-1))):
    sm.append(sm[-1]+ns[i])
ans=sm.pop()
sm.sort()
if k>1:
    ans+=sum(sm[-k+1:])
print(ans)





import sys

n, k = list(map(int,sys.stdin.readline().strip().split()))
a = list(map(int,sys.stdin.readline().strip().split()))
L = [a[-1]] * n
for i in range (1, n):
    L[i] = L[i-1] +a[n-i-1]
x = L.pop()
L.sort()
for i in range (0, k-1):
    x = x + L[n-2-i]
print(x)

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


n,k=mi()

l=lm()

running=[0]*(n-1)

for i in range(len(l)-1):
	if i==0:
		running[i]=(l[i],i+1)
	else:
		running[i]=(running[i-1][0]+l[i],i+1)

running.sort()

sliced=running[:k-1]

sliced.sort(key= lambda x: x[1])

cost=0
last=0
#print(sliced)
for i in range(len(sliced)):
	
	cost+=(i+1)*sum(l[last:sliced[i][1]])
	last=sliced[i][1]

cost+=k*sum(l[last:])


print(cost)




		




n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
ruiseki = [0]*(n+1)
ans = 0
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]
bb = sorted(ruiseki[1:n])

ans += ruiseki[-1]*k
for i in range(k-1):
    ans -= bb[i]
print(ans)





li = input().split()
n = int(li[0])
k = int(li[1])
a = input().split()
for i in range(n):
	a[i] = int(a[i])
for i in range(n-2,-1,-1):
	a[i] += a[i+1]
sa = sorted(a[1:])
ans = a[0]
for i in range(k-1):
	ans += sa[n-2-i]
print(ans)

import math
n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
b=[]
a.reverse()
counter=0
for i in range(n-1):
    counter+=a[i]
    b.append(counter)
b.sort(reverse=True)
print(sum(b[:k-1])+sum(a))


n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==1:
    print(a[0])
else:
    p=[a[-1]]+[0]*(n-2)
    for i in range(n-2):
        p[i+1]=p[i]+a[-i-2]
    j=p[-1]+a[0]
    p.sort(reverse=True)
    print(j+sum(p[:k-1]))

n, k = map(int, input().split())
a = list(map(int, input().split()))
p = [0]
for x in a[::-1]:
    p.append(p[-1] + x)
ans = p[-1] + sum(sorted(p[1:-1])[n - k:])
print(ans)

n, k = map(int, input().split())
a = list(map(int, input().split()))
p = [0]
for x in a[::-1]: p.append(p[-1] + x)
print(p[-1] + sum(sorted(p[1:-1])[n - k:]))

#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

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

    b = [0 for i in range(n)]
    for i in range(n-1,-1,-1):
        if i == n-1:
            b[i] = a[i]
        else:
            b[i] = b[i+1] + a[i]
    ans = b[0]
    b[1:] = sorted(b[1:])
    k -= 1
    for i in range(n-1,-1,-1):
        if k == 0:
            break
        ans += b[i]
        k -= 1
    print(ans)
__starting_point()

import heapq
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = [0 for i in range(n)]
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
x = s.pop()
x *= k

heapq.heapify(s)
for _ in range(k - 1):
    x -= heapq.heappop(s)
print(x)



n, k = map(int, input().split())
a = list(map(int, input().split()))
p = [0]
for i in a[ : : -1]:
    p.append(p[-1] + i)
p = p[ : : -1]
ans = p[0]
ans += sum(sorted(p[1: -1], reverse = True)[ : k - 1])
print(ans)

n, k = map(int, input().split())
a = list(map(int, input().split()))
p = [0]
for x in a[::-1]: p.append(p[-1] + x)
print(p[-1] + sum(sorted(p[1:-1])[n - k:]))

from sys import stdin,stdout
from itertools import combinations
from collections import defaultdict,OrderedDict
import math
import heapq

def listIn():
    return list((list(map(int,stdin.readline().strip().split()))))

def stringListIn():
    return([x for x in stdin.readline().split()])
    
def intIn():
    return (int(stdin.readline()))

def stringIn():
    return (stdin.readline().strip())

def __starting_point():
    n,k=listIn()
    a=listIn()
    arr=[a[0]]+[0]*(n-1)
    
    for i in range(1,n):
        arr[i]=arr[i-1]+a[i]
    
    #print(*arr)
    max_cost=arr[n-1]*k
    
    b=sorted(arr[:n-1])
    for i in range(k-1):
        max_cost-=b[i]
    
    print(max_cost)
        
    

__starting_point()

# cf_contests E66
import sys
input = sys.stdin.readline
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
s = 0
p = []
for i in range(n - 1, 0, -1):
    s += a[i]
    p.append(s)
p.sort()
p.reverse()
res = s + a[0]
for i in range(k-1):
    res += p[i]
print(res)


n, k = list(map(int, input().strip().split(' ')))
a = list(map(int, input().strip().split(' ')))
cnt = []
cnt.append(a[-1])
for i in range(1, n):
 cnt.append(cnt[i-1] + a[-(i+1)])
ans = cnt[-1]
del cnt[-1]
cnt.sort(reverse=True)
ans += sum(cnt[:(k-1)])
print(ans)


# AC
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = self.next_line()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_line(self):
        return sys.stdin.readline().split()

    def next_ints(self):
        return [int(x) for x in sys.stdin.readline().split()]

    def next_int(self):
        return int(next(self))

    def solve(self):
        n, k = self.next_ints()
        x = self.next_ints()
        ss = []
        s = 0
        for a in x[::-1]:
            s += a
            ss.append(s)
        ss = sorted(ss[:-1], reverse=True)
        print(s + sum(ss[:k - 1]))


def __starting_point():
    Main().solve()

__starting_point()

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

suffixSum = [nums[-1]]

for i in nums[-2::-1]:
    suffixSum.append(suffixSum[-1] + i)


suffixSum = suffixSum[:-1]
suffixSum.sort(reverse=True)

ans = sum(nums)
ans += sum(suffixSum[:k-1])

print(ans)

def __starting_point():
    n,k = map(int, input().split())
    aa = list(map(int, input().split()))
    ss = [0]
    for a in reversed(aa):
        ss.append(ss[-1] + a)
        
    ss = ss[1:]
    if k == 1:
        print(ss[-1])
        return
    print(ss[-1] + sum(sorted(ss[:-1])[-(k-1):]))
__starting_point()

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
s = 0
for x in a[::-1]:
    s += x
    b.append(-s)
if k == 1:
    print(-b[-1])
else:
    d = sorted(b[:-1])
    print(-sum(d[:k-1]) - b[-1])