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 os
import math
import statistics

true = True;
false = False;

# from collections import defaultdict, deque
from functools import reduce

is_dev = 'vscode' in os.environ

if is_dev:
    inF = open('in.txt', 'r')
    outF = open('out.txt', 'w')

def ins():
    return list(map(int, input_().split(' ')))

def inss():
    return list(input_().split(' '))

def input_():
    if is_dev:
        return inF.readline()[:-1]
    else:
        return input()
    
def ranin():
    return range(int(input_()))

def print_(data):
    if is_dev:
        outF.write(str(data)+'\n')
    else:
        print(data)
        
epsilon = 1e-7


n, k = ins()
a = ins()
cuts = k - n

def score(x, cut):
    return (
        (x // cut)**2 * (cut - x % cut) 
    ) + (
        (x // cut + 1)**2 * (x % cut) 
    )

def gain(t, i):
#     print(t,i, score(t, i - 1) - score(t, i))
    return score(t, i - 1) - score(t, i)


from heapq import heappop, heappush
pq = []

ts = 0
for i in a:
    ts += i**2
    g = gain(i, 2)
    heappush(pq, (-g, i, 2))

for i in range(cuts):
    next_largest_gain = heappop(pq)
    ts += next_largest_gain[0]
    g = gain(next_largest_gain[1], next_largest_gain[2]+1)
    heappush(pq, (-g, next_largest_gain[1],next_largest_gain[2]+1))
print_(ts)
    
if is_dev:
    outF.close()
    def compare_file():
        print(open('out.txt', 'r').read() == open('outactual.txt', 'r').read())
    compare_file()
