There are some rabbits in Singapore Zoo. To feed them, Zookeeper bought n carrots with lengths a_1, a_2, a_3, …, a_n. However, rabbits are very fertile and multiply very quickly. Zookeeper now has k rabbits and does not have enough carrots to feed all of them. To solve this problem, Zookeeper decided to cut the carrots into k pieces. For some reason, all resulting carrot lengths must be positive integers.

Big carrots are very difficult for rabbits to handle and eat, so the time needed to eat a carrot of size x is x^2.

Help Zookeeper split his carrots while minimizing the sum of time taken for rabbits to eat the carrots.

Input

The first line contains two integers n and k (1 ≤ n ≤ k ≤ 10^5): the initial number of carrots and the number of rabbits.

The next line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^6): lengths of carrots.

It is guaranteed that the sum of a_i is at least k.

Output

Output one integer: the minimum sum of time taken for rabbits to eat carrots.

Examples

Input


3 6
5 3 1


Output


15


Input


1 4
19


Output


91

Note

For the first test, the optimal sizes of carrots are \{1,1,1,2,2,2\}. The time taken is 1^2+1^2+1^2+2^2+2^2+2^2=15

For the second test, the optimal sizes of carrots are \{4,5,5,5\}. The time taken is 4^2+5^2+5^2+5^2=91.
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class e1428 implements Runnable{
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new e1428(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		//int t = scan.nextInt();
		int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {
		static final int oo = Integer.MAX_VALUE;
		static final long OO = Long.MAX_VALUE;

		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			int[] arr = sc.readArray(N);

			int[] div = new int[N];
			long[] curWeight = new long[N];
			Arrays.fill(div, 1);
			PriorityQueue<tup> pq = new PriorityQueue<>(new tup());
			for(int i = 0; i < N; i++) {
				long divide = arr[i] / (long)(div[i]);
				long mod = arr[i] % (long)(div[i]);
				
				curWeight[i] = (divide+1) * (divide+1) * mod;
				curWeight[i] += divide * divide * (div[i] - mod);
				
				divide = arr[i] / (long)(div[i]+1);
				mod = arr[i] % (long)(div[i]+1);
				
				long a = (divide+1) * (divide+1) * mod;
				a += divide * divide * (div[i]+1 - mod);
				pq.add(new tup(i, curWeight[i] - a));
			}
			
			while(N < K) {
				tup t = pq.poll();
				int i = t.a;
				div[i]++;
				curWeight[i] = curWeight[i] - t.b;
				long divide = arr[i] / (long)(div[i]+1);
				long mod = arr[i] % (long)(div[i]+1);
				
				long a = (divide+1) * (divide+1) * mod;
				a += divide * divide * (div[i]+1 - mod);
				
				pq.add(new tup(i, curWeight[i] - a));
				K--;
			}
			
			//dbg(Arrays.toString(div));
			
			long sumTime = 0;
			for(int i = 0; i < N; i++) {
				long divide = arr[i] / (long)(div[i]);
				long mod = arr[i] % (long)(div[i]);
				
				sumTime += (divide+1) * (divide+1) * mod;
				sumTime += divide * divide * (div[i] - mod);
			}
			
			out.println(sumTime);
		}
		
	}
	static long modInverse(long N, long MOD) {
		return binpow(N, MOD - 2, MOD);
	}
	static long modDivide(long a, long b, long MOD) {
		a %= MOD;
		return (binpow(b, MOD-2, MOD) * a) % MOD;
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static int[] reverse(int a[]) 
    { 
        int[] b = new int[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static long[] reverse(long a[]) 
    { 
        long[] b = new long[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}
	
	static void sort(int[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	
	static class tup implements Comparable<tup>, Comparator<tup>{
		int a; long b;
		tup(int a,long b){
			this.a=a;
			this.b=b;
		}
		public tup() {
		}
		@Override
		public int compareTo(tup o){
			return Long.compare(o.b,b);
		}
		@Override
		public int compare(tup o1, tup o2) {
			return Long.compare(o2.b, o1.b);
		}
		
		@Override
	    public int hashCode() {
			return Objects.hash(a, b);
	    }
 
	    @Override
	    public boolean equals(Object obj) {
	    	if (this == obj)
                return true;
	    	if (obj == null)
                return false;
	    	if (getClass() != obj.getClass())
                return false;
	    	tup other = (tup) obj;
	    	return a==other.a && b==other.b;
	    }
	    
	    @Override
	    public String toString() {
	    	return a + " " + b;
	    }
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		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;
		}
		
		int[] readArray(int size) {
			int[] a = new int[size];
			for(int i = 0; i < size; i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		long[] readLongArray(int size) {
			long[] a = new long[size];
			for(int i = 0; i < size; i++) {
				a[i] = nextLong();
			}
			return a;
		}
	}
	
	static void dbg(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(long[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(boolean[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	static void dbg(Object... args) {
        for (Object arg : args)
            System.out.print(arg + " ");
        System.out.println();
    }
}