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.ByteArrayInputStream;
import java.io.File;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class E {
  int USE_FILE = 0;
  int HAS_TESTCASES = 0;
  String INPUT = "3 6\n" + "5 3 1\n" + "";
  void solve(int caseNr) {
    int n = in.nextInt();
    int k = in.nextInt();
    List<Integer> a = next_int_list(n);
    PriorityQueue<Carrot> pri_queue = new PriorityQueue<>(Collections.reverseOrder());
    for (Integer val : a) {
      Carrot carrot = new Carrot(val);
      pri_queue.add(carrot);
    }
    int perform_cuts = k - n;
    while (perform_cuts-- > 0) {
      Carrot c = pri_queue.poll();
      c.cut_carrot();
      pri_queue.add(c);
    }
    long result = 0;
    while (pri_queue.size() > 0) {
      Carrot c = pri_queue.poll();
      result += c.current_val;
    }
    System.out.println(result);
  }
  class Carrot implements Comparable<Carrot> {
    int size;
    int nr_pieces = 1;
    int largest_piece;
    public Carrot(int size) {
      this.size = size;
      this.largest_piece = size;
      List<Integer> one_piece = new ArrayList<>();
      one_piece.add(size);
      current_val = currentVal();
      next_val = nextVal();
      gain = current_val - next_val;
    }
    public void cut_carrot() {
      nr_pieces++;
      if (nr_pieces > size)
        nr_pieces = size;
      int div = size / nr_pieces;
      if (size % nr_pieces > 0) {
        largest_piece = div + 1;
      } else {
        largest_piece = div;
      }
      current_val = next_val;
      next_val = nextVal();
      gain = current_val - next_val;
    }
    long current_val;
    long next_val;
    long gain;
    long currentVal() {
      long w1 = size / nr_pieces;
      long w2 = w1 + 1;
      int p2 = size % nr_pieces;
      int p1 = nr_pieces - p2;
      long val = p1 * w1 * w1 + p2 * w2 * w2;
      return val;
    }
    long nextVal() {
      long w1 = size / (nr_pieces + 1);
      long w2 = w1 + 1;
      int p2 = size % (nr_pieces + 1);
      int p1 = (nr_pieces + 1) - p2;
      long val = p1 * w1 * w1 + p2 * w2 * w2;
      return val;
    }
    @Override
    public String toString() {
      return String.format("size=%d piece=%d", size, largest_piece);
    }
    @Override
    public int compareTo(Carrot c2) {
      return Long.compare(this.gain, c2.gain);
    }
  }
  public static List<Integer> next_int_list(int n) {
    List<Integer> a = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      a.add(in.nextInt());
    }
    return a;
  }
  static boolean LOCAL = java.lang.System.getProperty("ONLINE_JUDGE") == null;
  static Scanner in;
  static PrintWriter output_writer = new PrintWriter(java.lang.System.out);
  static class System {
    static PrintWriter out = null;
  }
  void setup() throws Exception {
    System.out = output_writer;
    if (LOCAL && USE_FILE == 0) {
      java.lang.System.setIn(new ByteArrayInputStream(INPUT.getBytes()));
      in = new Scanner(java.lang.System.in);
    }
    if (LOCAL && USE_FILE > 0) {
      String filename = String.format("in/cf%d.txt", USE_FILE);
      File inputFile = new File(filename);
      in = new Scanner(inputFile);
      System.out.printf("[%s]\n", filename);
    }
    if (!LOCAL) {
      in = new Scanner(java.lang.System.in);
    }
    long startTime = java.lang.System.currentTimeMillis();
    int t = HAS_TESTCASES > 0 ? in.nextInt() : 1;
    for (int i = 1; i <= t; i++) {
      solve(i);
    }
    in.close();
    if (LOCAL) {
      System.out.printf("[%dms]\n", java.lang.System.currentTimeMillis() - startTime);
    }
    output_writer.flush();
  }
  public static void main(String[] args) throws Exception {
    new E().setup();
  }
}
