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

public class E
{
   public static void main(String[] args) throws IOException
   {
      FastScanner sc = new FastScanner();
      PrintWriter out = new PrintWriter(System.out);
      long n = sc.nextLong();
      long k = sc.nextLong();
      PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
      for(int i = 0; i < n; i++){
         long a = sc.nextLong();
         pq.add(new Pair(a, 1L)) ;
      }
      for(int i = 0; i < k-n; i++){
         Pair p = pq.poll();
         if(p.b < p.a){
            p.b++;
         }
         pq.add(p);
      }
      long ans = 0;
      while(!pq.isEmpty()){
         Pair p = pq.poll();
         ans += calc(p.a, p.b);
      }
      out.println(ans);
      out.close();
   }
   static long calc(long a, long b){
      long ans = 0;
      long div = a/b;
      long num = (a)%(b);
      ans += num*(div+1)*(div+1);
      ans += (b-num)*(div*div);
      return ans;
   }
   static class Pair implements Comparable<Pair>{
      long a, b;
      public Pair(long x, long y){
         this.a = x;
         this.b = y;
      }
      public int compareTo(Pair o){
         long val = calc(this.a, this.b) - calc(this.a, this.b+1);
         long oval = calc(o.a, o.b) - calc(o.a, o.b+1);
         if(val < oval){
            return 1;
         }
         else if(val == oval){
            return 0;
         }
         else{
            return -1;
         }
      }
   }
   static class FastScanner {
      private int BS = 1 << 16;
      private char NC = (char) 0;
      private byte[] buf = new byte[BS];
      private int bId = 0, size = 0;
      private char c = NC;
      private double cnt = 1;
      private BufferedInputStream in;
   
      public FastScanner() {
         in = new BufferedInputStream(System.in, BS);
      }
   
      public FastScanner(String s) {
         try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
         } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
         }
      }
   
      private char getChar() {
         while (bId == size) {
            try {
               size = in.read(buf);
            } catch (Exception e) {
               return NC;
            }
            if (size == -1) 
               return NC;
            bId = 0;
         }
         return (char) buf[bId++];
      }
   
      public int nextInt() {
         return (int) nextLong();
      }
   
      public int[] nextInts(int N) {
         int[] res = new int[N];
         for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
         }
         return res;
      }
   
      public long[] nextLongs(int N) {
         long[] res = new long[N];
         for (int i = 0; i < N; i++) {
            res[i] = nextLong();
         }
         return res;
      }
   
      public long nextLong() {
         cnt = 1;
         boolean neg = false;
         if (c == NC) c = getChar();
         for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
         }
         long res = 0;
         for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
         }
         return neg ? -res : res;
      }
   
      public double nextDouble() {
         double cur = nextLong();
         return c != '.' ? cur : cur + nextLong() / cnt;
      }
   
      public double[] nextDoubles(int N) {
         double[] res = new double[N];
         for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
         }
         return res;
      }
   
      public String next() {
         StringBuilder res = new StringBuilder();
         while (c <= 32) c = getChar();
         while (c > 32) {
            res.append(c);
            c = getChar();
         }
         return res.toString();
      }
   
      public String nextLine() {
         StringBuilder res = new StringBuilder();
         while (c <= 32) c = getChar();
         while (c != '\n') {
            res.append(c);
            c = getChar();
         }
         return res.toString();
      }
   
      public boolean hasNext() {
         if (c > 32) 
            return true;
         while (true) {
            c = getChar();
            if (c == NC) 
               return false;
            else if (c > 32) 
               return true;
         }
      }
   }

   static void ASSERT(boolean assertion, String message) {
      if (!assertion) throw new AssertionError(message);
   }

}