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.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class ProblemR1E {
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(System.out);

		StringTokenizer info = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(info.nextToken());
		int k = Integer.parseInt(info.nextToken());

		StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
		a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = Long.parseLong(tokenizer.nextToken());
		}
		cuts = new int[n];

		// binary search to do it in x time
		//writer.println(binarySearch(k));
		writer.println(getTime(k));

		reader.close();
		writer.close();
	}
	static long[] a;
	static int[] cuts;
	static PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingLong(index -> {
		return -(getTime(a[index], cuts[index]) - getTime(a[index], cuts[index] + 1));
	}));
	public static long getTime(int k) {
		int n = a.length;
		pq.clear();
		Arrays.fill(cuts, 1); // start with 1 piece
		// descending pq
		for (int i = 0; i < n; i++) {
			pq.add(i);
		}
		for (int i = 0; i < k - n; i++) {
			int polledIndex = pq.poll();
			cuts[polledIndex]++;
			pq.add(polledIndex);
		}
		long totalTime = 0;
		for (int i = 0; i < n; i++) {
			totalTime += getTime(a[i], cuts[i]);
		}
		return totalTime;
	}
	public static long getTime(long x, int numCuts) {
		long floor = x / numCuts;
		long ceil = floor + 1;
		long mod = x % numCuts;
		return (numCuts - mod) * floor * floor + mod * ceil * ceil;
	}
}
