You are given an array a_1, a_2, ..., 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 ∑_{i=1}^{n} (a_i ⋅ 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 ⋅ 1 - 2 ⋅ 1 - 3 ⋅ 1 + 4 ⋅ 2 - 5 ⋅ 2 + 6 ⋅ 3 - 7 ⋅ 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 ≤ k ≤ n ≤ 3 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n ( |a_i| ≤ 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
	import java.io.*;
	import java.util.*;
	import java.math.*;
	
	 
	 public class Main	{
	   static class Pair implements Comparable<Pair>{

		   int a;
		   long b;
		   public Pair(int x,long y){a=x;b=y;}
		   public int compareTo(Pair p){
				 return Long.compare(a, p.a);
		   }
//		@Override
//		public int hashCode() {
//			final int prime = 31;
//			int result = 1;
//			result = prime * result + a;
//			result = prime * result + b;
//		   
//			return result;
//		}
//		@Override
//		public boolean equals(Object obj) {
//			Pair cur = (Pair)obj;
//			if((a==cur.a && b==cur.b))return true;
//			return false;
//		}
	 }
	  static class cell{
		  int a, b;
		  public cell(int x, int y) {
			  a = x;
			  b = y;
		  }
	  }
	static class TrieNode{
		int cnt;
		TrieNode[]child;
		public TrieNode() {
			cnt = 0;
			child = new TrieNode[26];
		}
	}
	  public static long gcd(long a,long b)
	  {
	    if(a<b)
	      return gcd(b,a);
	    if(b==0)
	      return a;
	    return gcd(b,a%b);
	    
	  }
	  static int lcm(int a,int b) {
		  return  a*b / (int)gcd(a,b);
	  }
	  
	  static long mod = 998244353;//(long)(1e9+7); //
	   
	    public static void main(String[] args) throws Exception {
	       new Thread(null, null, "Anshum Gupta", 99999999) {
	            public void run() {
	                try {
	                    solve();
	                } catch(Exception e) {
	                    e.printStackTrace();
	                    System.exit(1);
	                }
	            }
	        }.start();
	    }
	
	static long pow(long x,long y){
	    if(y == 0)return 1;
	    if(y==1)return x;
	    long a = pow(x,y/2);
	    a = (a*a)%mod;
	    if(y%2==0){
	        return a;
	    }
	    return (a*x)%mod;
	}
	
	static long mxx;
	static int mxN = (int)(1e4);
	static int mxV = (int)(2e5);
	static long[]fact,inv_fact;
	static long my_inv(long a) {
		return pow(a,mod-2);
	}
	static long bin(int a,int b) {
		if(a < b || a<0 || b<0)return 0;
	    return ((fact[a]*inv_fact[a-b])%mod * inv_fact[b])%mod;
	}
		static ArrayList<ArrayList<Integer>>adj;
		static boolean[][]vis;
	static void make_facts() {
	  fact=new long[mxN];
	  inv_fact = new long[mxN];
	  fact[0]=inv_fact[0]=1L;
	  for(int i=1;i<mxN;i++) {
		   fact[i] = (i*fact[i-1])%mod;
		   inv_fact[i] = my_inv(fact[i]);
	  }
	}
	
	 public static void solve() throws Exception {
	   // solve the problem here
	   MyScanner s = new MyScanner();
	        out = new PrintWriter(new BufferedOutputStream(System.out), true);
	        int tc = 1;//s.nextInt();
	        mxx = (long)(1e18+5);
		        make_facts(); 
//		        int mod = (int)1e9+7;
	        
	        while(tc-->0){
	        	int n = s.nextInt();
	        	int k = s.nextInt();
	        	int[]a = new int[n+1];
	        	boolean[]all_neg = new boolean[n+1];
	        	Arrays.fill(all_neg, true);
	        	long sm = 0;
	        	for(int i=1;i<=n;i++) {
	        		a[i] = s.nextInt();
	        		sm += a[i];
	        		if(!all_neg[i-1]) {
	        			all_neg[i] = false;
	        			continue;
	        		}
	        		if(a[i] >= 0)
	        			all_neg[i] = false;
	        	}
	        	if(k == 1) {
	        		out.println(sm);
	        		return;
	        	}
	        	long suf[] = new long[n+2];
	        	PriorityQueue<Long> pq = new PriorityQueue<Long>(Collections.reverseOrder());
	        	for(int i=n;i>=1;i--) {
	        		suf[i] = suf[i+1] + a[i];
	        		if(i > 1)
	        		pq.add(suf[i]);
	        	}
	        	long res = sm;
	        	for(int i=0;i<k-1;i++) {
	        		res += pq.poll();
	        	}
	        	out.println(res);
	        }
	        
	        	
	           
	        out.flush();
	}
	 
	     
	 
	 
	 
	    //-----------PrintWriter for faster output---------------------------------
	    public static PrintWriter out;
	 
	    //-----------MyScanner class for faster input----------
	    public static class MyScanner {
	        BufferedReader br;
	        StringTokenizer st;
	 
	        public MyScanner() {
	            br = new BufferedReader(new InputStreamReader(System.in));
	        }
	 
	        String next() {
	            while (st == null || !st.hasMoreElements()) {
	                try {
	                    st = new StringTokenizer(br.readLine());
	                } catch (IOException e) {
	                    e.printStackTrace();
	                }
	            }
	            return st.nextToken();
	        }
	 
	        int nextInt() { return Integer.parseInt(next()); }
	        long nextLong() { return Long.parseLong(next()); }
	        double nextDouble() { return Double.parseDouble(next()); }
	         
	        String nextLine(){
	            String str = "";
	            try {
	                str = br.readLine();
	            } catch (IOException e) {
	                e.printStackTrace();
	            }
	            return str;
	        }
	    }
	    //--------------------------------------------------------
	}
