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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class E_Carrots {
	static int n;
	public static void main(String[] args) throws NumberFormatException, IOException
	{
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
		String[] in = scan.readLine().split(" ");
		
		n = parse(in[0]);
		int k = parse(in[1]);
		
		PriorityQueue<Carrot> set = new PriorityQueue<Carrot>();
		long ans = 0;
		in = scan.readLine().split(" ");
		int val;
		for(int i = 0; i < n; i++)
		{
			val = parse(in[i]);
			if(val == 1)
			{
				k--;
				ans ++;
				continue;
			}
			set.add( new Carrot(parse(in[i]), i) );
		}
		
		Carrot temp;
		k -= set.size();
		
		while(k > 0)
		{
			temp = set.poll();
				
			temp.cut();
			k--;
			set.add(temp);
		}
	
		
		for(Carrot c : set)
			ans += c.time();
		
		System.out.println(ans);
	}

	public static int parse(String num)
	{
		return Integer.parseInt(num);
	}
	
	static class Carrot implements Comparable<Carrot>
	{
		long maxLen, length;
		long numCarrots;
		int id;
		
		public Carrot(int size, int i)
		{
			length = size;
			maxLen = size;
			numCarrots = 1;
			id = i;
		}
		
		public long cut()
		{
			numCarrots ++;
			maxLen = length / numCarrots + (length % numCarrots == 0 ? 0 : 1);
			return 1;
		}
		
		public long time()
		{
			long remain = length % numCarrots;
			long len = length / numCarrots;
			
			return remain * (len + 1)  * (len + 1) + (numCarrots - remain) * len * len;
		}
		
		public long delta()
		{
			if(length == 1 || numCarrots == length) return 0;
			
			long remain = length % (numCarrots + 1);
			long len = length / (numCarrots + 1);
			
			return time() - (remain * (len + 1) * (len + 1) + ((numCarrots+1) - remain) * len * len);
		}

		@Override
		public int compareTo(Carrot c) {
			long delta = delta();
			long cDelta = c.delta();
			
			if(delta == cDelta)
				return id - c.id;
			
			return Long.compare(cDelta, delta);
		}
		
		public String toString()
		{
			return length + " split into " + numCarrots + " carrots"; 
		}
		
	}
}
