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.
//make sure to make new file!
import java.io.*;
import java.util.*;

public class ERR1{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      long[] array = new long[n];
      st = new StringTokenizer(f.readLine());
      
      long answer = 0L;
      
      PriorityQueue<Place> pq = new PriorityQueue<Place>(10, Collections.reverseOrder());
      
      for(int k = 0; k < n; k++){
         array[k] = Long.parseLong(st.nextToken());
         answer += array[k]*array[k];
         pq.add(new Place(array[k]));
      }
      
      for(int k = n; k < m; k++){
         Place p = pq.poll();
         answer -= p.nextsplit;
         if(p.x < p.i-1){
            //add it back
            p.x++;
            p.cursplit = p.cursplit-p.nextsplit;
            p.nextsplit = p.cursplit-split(p.i,p.x+1);
            pq.add(p);
         }
      }
      
      out.println(answer);
         
      
      
      
      
      
      
      
      
      
      
      
      out.close();
   }
   
   public static long split(long i, long x){
      long numi = i%x;
      long ix = i/x;
      return ((ix+1)*(ix+1)*numi + ix*ix*(x-numi));
   }
    
   public static class Place implements Comparable<Place>{
      long i;         //starting number
      long x;         //splits so far
      long cursplit;    //current value of split
      long nextsplit;   //improvement if split again
      
      public Place(long a){
         i = a;
         x = 1L;
         cursplit = i*i;
         nextsplit = cursplit-split(i,2L);
      }
      
      //compare by nextsplit
      public int compareTo(Place p){
         if(nextsplit > p.nextsplit) return 1;
         if(nextsplit < p.nextsplit) return -1;
         return 0;
      }
      public String toString(){
         return i + " " + x + " " + cursplit+ " " + nextsplit;
      }
   }
   
      
}