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 javax.print.DocFlavor;
import javax.swing.text.html.parser.Entity;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    static FastScanner sc;
    static PrintWriter pw;
    static final long INF = 2000000000000000000l;
    static final int MOD = 1000000007;
    static final int N = 1005;
    static List<List<B>> gr;
    static List<List<B>> gi;

    static class A {
        int h;
        int w;
        int pos;
        A(int l, int r, int pos) {
            this.h = l;
            this.w = r;
            this.pos = pos;
        }

        @Override
        public String toString() {
            return "[ " + h + " " + w + " " + pos + " ]";
        }
    }

    static class B {
        int x;
        int y;
        B(int w, int pos) {
            this.x = w;
            this.y = pos;
        }

        @Override
        public String toString() {
            return "[ " + x + " " + y + " ]";
        }
    }

    static int mul(int a, int b) {
        return (int) ((a * 1l * b) % MOD);
    }


    public static int pow(int a, int n) {
        int res = -1;
        while(n != 0) {
            if((n & 1) == 1) {
                res = mul(res, a);
            }

            a = mul(a, a);
            n >>= 1;
        }

        return res;
    }

    public static int inv(int a) {
        return pow(a, MOD-2);
    }

    public static List<Integer> getPrimes() {
        List<Integer> ans = new ArrayList<>();
        boolean[] prime = new boolean[N];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for(int i = 2; i < N; ++i) {
            if(prime[i]) {
                ans.add(i);
                if (i * 1l * i <= N)
                    for (int j = i * i; j < N; j += i)
                        prime[j] = false;
            }
        }

        return ans;
    }

    public static void addElem(TreeMap<Integer, Integer> m, int val) {
        if(m.containsKey(val)) m.put(val, m.get(val) + 1);
        else m.put(val , 1);
    }

    public static void removeElem(TreeMap<Integer, Integer> m, int val) {
        Integer cnt = m.get(val);
        if(cnt == null) return;

        if(cnt > 1) m.put(val , cnt - 1);
        else m.remove(val);
    }

    public static long sqr(long x) {
        return x * x;
    }

    public static long getSum(long num, long times) {
        long res = 0;
        res += (num % times) * sqr(num / times + 1);
        res += (times - (num % times)) * sqr(num / times);

        return res;
    }

    public static long getDiff(long x, long num_x) {
        return getSum(x, num_x) - getSum(x, num_x + 1);
    }

    public static void solve() throws IOException {
        int n = sc.nextInt(), k = sc.nextInt();
        long[] a = new long[n];
        long[] b = new long[n];
        PriorityQueue<Integer> q = new PriorityQueue<>( (Integer l, Integer r) -> {
            long x = getDiff(a[r], b[r]), y = getDiff(a[l], b[l]);
            if (x > y) return 1;
            else if (x < y) return -1;
            else return 0;
        });
        for(int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
            b[i] = 1;
            q.add(i);
        }

        for(int i = 0; i < k - n; ++i) {
            int j = q.poll();
            b[j]++;
            q.add(j);
        }

        long sum = 0;
        for(int i = 0; i < n; ++i) {
            sum += getSum(a[i], b[i]);
        }
        pw.println(sum);
    }


    public static void main(String[] args) throws IOException {
        sc = new FastScanner(System.in);
        pw = new PrintWriter(System.out);

        int xx = 1;
        while(xx > 0) {
            solve();
            xx--;
        }
        pw.close();

    }


}

class FastScanner {
    static StringTokenizer st = new StringTokenizer("");
    static BufferedReader br;

    public FastScanner(InputStream inputStream) {
        br = new BufferedReader(new InputStreamReader(inputStream));
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

}