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

public class Main
{
	PrintWriter out = new PrintWriter(System.out);
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok = new StringTokenizer("");
    String next() throws IOException {
        if (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); }
        return tok.nextToken();
    }
    int ni() throws IOException { return Integer.parseInt(next()); }
    long nl() throws IOException { return Long.parseLong(next()); }
    
    long mod=1000000007;
    
    void solve() throws IOException {
        int n=ni(),k=ni();
        PriorityQueue<carrot>PQ=new PriorityQueue(new carrotcomparator());
        for (int i=0;i<n;i++) {
            long u=ni();
            long cc=u*u;
            long nc=(u/2)*(u/2)*2;
            if (u%2==1) nc=(u/2+1)*(u/2+1)+(u/2)*(u/2);
            PQ.add(new carrot(u,u,1,cc,nc));
        }
        
        while (n<k) {
            carrot t=PQ.poll();
            //t.print();
            t.d++;
            t.mcv=t.a/t.d+(t.a%t.d>0?1:0);
            t.cc=t.nc;
            int m=t.d+1;
            long cv=t.a/m+(t.a%m>0?1:0);
            t.nc=0;
            if (t.a%m>0) {
                t.nc=cv*cv*(t.a%m);
                m-=(t.a%m);
                cv--;
            }
            t.nc=t.nc+cv*cv*m;
            PQ.add(t);
            //t.print();
            n++;
        }
        
        long total=0;
        while (PQ.size()>0) {
            carrot t=PQ.poll();
            /*if (t.a%t.d==0) {
                long na=t.d;
                na=na*t.mcv*t.mcv;
                total+=na;
            } 
            else {
                int xs=t.a%t.d;
                long na=xs;
                na=na*t.mcv*t.mcv;
                total+=na;
                na=t.d-xs;
                t.mcv--;
                na=na*t.mcv*t.mcv;
                total+=na;
            }*/
            total+=t.cc;
        }
        
        out.println(total);
        out.flush();
    }
    
    class carrotcomparator implements Comparator<carrot> {
        public int compare(carrot a,carrot b) {
            //long diff1=a.cc-a.nc;
            //long diff2=b.cc-b.nc;
            return Long.compare(b.cc-b.nc,a.cc-a.nc);
            //else return Long.compare(b.mcv,a.mcv);
        }
    }
    
    class carrot {
        long mcv,a;
        int d;
        long cc,nc;
        carrot(long x,long y,int z,long p,long q) {
            mcv=x; a=y; d=z; cc=p; nc=q;
        }
        void print() {
            out.println(mcv+" "+a+" "+d+" "+cc+" "+nc);
        }
    }
    
    int gcd(int a,int b) { return(b==0?a:gcd(b,a%b)); }
    long gcd(long a,long b) { return(b==0?a:gcd(b,a%b)); }
    long mp(long a,long p) { long r=1; while(p>0) { if ((p&1)==1) r=(r*a)%mod; p>>=1; a=(a*a)%mod; } return r; }
    
    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}