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.
from collections import Counter, defaultdict, deque
import bisect
import heapq
from sys import stdin, stdout
from itertools import repeat
import math
import random
 
# sys.stdin = open('input')
 
def mod(x, y, mod):
    re = 1
    now = x
    while y:
        if y&1:
            re *= now
            re %= mod
        y >>= 1
        now = (now*now)%mod
    return re
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
def ggcd(x, y):
    if y:
        return ggcd(y, x%y)
    return x
 
MOD = int(1e9+7)
 
 
def my_main():
    T = 1
    for _ in range(T):
        n, k = inp()
        da = inp(True)
        hp = []
        idx = [1 for i in range(n)]
        def ff(p, l):
            w = p/l
            wp = p/l+1
            nwp = p%l
            nw = l-nwp
            return nw*w*w+nwp*wp*wp
        ans = 0

        for i in range(n):
            hp.append((ff(da[i], 2) - ff(da[i], 1), i))
        heapq.heapify(hp)
        for i in range(k-n):
            item, ii = hp[0]
            idx[ii] += 1
            ans += item
            heapq.heapreplace(hp, (ff(da[ii], idx[ii]+1) - ff(da[ii], idx[ii]), ii))
        for i in da:
           ans += i*i
        print ans

            
my_main()
