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.
// package com.company;
import java.util.*;
import java.lang.*;
import java.io.*;
//****Use Integer Wrapper Class for Arrays.sort()****
public class FQ5 {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] Args)throws Exception{
        FastReader scan=new FastReader(System.in);
        int t=1;
//        t=scan.nextInt();
        while(t-->0){
            int n=scan.nextInt();
            int k=scan.nextInt();
            Long[] arr=new Long[n];
            for(int i=0;i<n;i++){
                arr[i]=scan.nextLong();
            }
            long[] divs=new long[n];
            Arrays.fill(divs,1);
            long more=k-n;
            PriorityQueue<trip> pq=new PriorityQueue<>(n,new mc());
            for(int i=0;i<n;i++){
                pq.add(new trip(i,arr[i],1));
            }
            while(more>0){
                trip cur=pq.remove();
                divs[cur.x]++;
                cur.z++;
                pq.add(cur);
                more--;
            }
            long ans=0;
            for(int i=0;i<n;i++){
                ans+=val(arr[i],divs[i]);
            }
            out.println(ans);
        }
        out.flush();
        out.close();
    }
    static class mc implements Comparator<trip>{
        @Override
        public int compare(trip o1, trip o2) {
            long v1=val(o1.y,o1.z)+val(o2.y,o2.z+1);
            long v2=val(o1.y,o1.z+1)+val(o2.y,o2.z);
            if(v1>=v2){
                return -1;
            }
            return 1;
        }
    }
    static class trip{
        int x;
        long y;
        long z;
        trip(int x,long y,long z) {
            this.x = x;
            this.y = y;
            this.z=z;
        }
    }
    static long val(long len,long grp){
        long sq=len/grp;
        long gr=len%grp;
        long val=0;
        val+=sq*sq*(grp-gr);
        sq++;
        val+=sq*sq*gr;
        return val;
    }
    static class FastReader {

        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;

        FastReader(InputStream is) {
            in = is;
        }

        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }

        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
}
