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.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Coding {

    private static BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) {
        try {
            run();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void run() throws Exception {
        InputModule inp = new InputModule();
        OutputModule out = new OutputModule();
        int t = 1;
        while (t > 0) {
            long[] inps = inp.cinLongArray(2);
            int carrots = (int) inps[0];
            long parts = inps[1];
            long[] carSizes = inp.cinLongArray(carrots);
            long[] partCount = new long[carrots];
            long partSum = 0;
            long squareSum = 0;
            for(int i=0;i<carrots;++i) {
                partCount[i] = 1;
                partSum+=partCount[i];
                squareSum+=bestSquareSum(carSizes[i], partCount[i]);
            }
            PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    if (o2.value>o1.value) {
                        return 1;
                    } else {
                        return -1;
                    }
                }
            });
            for(int i=0;i<carrots;++i) {
                if (partCount[i]<carSizes[i]) {
                    long curSum = bestSquareSum(carSizes[i], partCount[i]);
                    long nextSum = bestSquareSum(carSizes[i], partCount[i] + 1);
                    long reduce = curSum - nextSum;
                    pq.add(new Pair(reduce, i));
                }
            }
            while (partSum<parts) {
                Pair  pp = pq.poll();
                squareSum-=pp.value;
                partCount[pp.index]++;
                if (partCount[pp.index]<carSizes[pp.index]) {
                    long curSum = bestSquareSum(carSizes[pp.index], partCount[pp.index]);
                    long nextSum = bestSquareSum(carSizes[pp.index], partCount[pp.index] + 1);
                    long reduce = curSum - nextSum;
                    pq.add(new Pair(reduce, pp.index));
                }
                partSum++;
            }
            out.printLong(squareSum);
            t--;
        }
    }

    private static long bestSquareSum(long val, long partCount) {
        long minValue = val/partCount;
        long maxValue = minValue+1;
        long maxValueCount = val%partCount;
        long minValueCount = partCount-maxValueCount;
        return minValueCount*minValue*minValue + maxValueCount*maxValue*maxValue;
    }

    private static class InputModule {
        private int cinInt() throws Exception {
            return Integer.parseInt(bi.readLine().split(" ")[0].trim());
        }

        private long cinLong() throws Exception {
            return Long.parseLong(bi.readLine().split(" ")[0].trim());
        }

        private Double cinDouble() throws Exception {
            return Double.parseDouble(bi.readLine().split(" ")[0].trim());
        }

        private int[] cinIntArray(int n) throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            int[] ar = new int[n];
            for (int i = 0; i < n; ++i) {
                ar[i] = Integer.parseInt(values[i]);
            }
            return ar;
        }

        private long[] cinLongArray(int n) throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            long[] ar = new long[n];
            for (int i = 0; i < n; ++i) {
                ar[i] = Long.parseLong(values[i]);
            }
            return ar;
        }
    }

    private static class OutputModule {
        private void printInt(int ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printLong(long ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printDouble(Double ans) throws Exception {
            writer.append(String.format("%.10f", ans));
            writer.append("\n");
            writer.flush();
        }

        private void printIntArray(int[] ans) throws Exception {
            for (int i = 0; i < ans.length; ++i) {
                writer.append(ans[i] + " ");
            }
            writer.append("\n");
            writer.flush();
        }

        private void printLongArray(long[] ans) throws Exception {
            for (int i = 0; i < ans.length; ++i) {
                writer.append(ans[i] + " ");
            }
            writer.append("\n");
            writer.flush();
        }
    }

    private static class Pair {
        long value;
        int index;
        public Pair(long value, int idx) {
            this.value = value;
            this.index = idx;
        }
    }
}