There are some rabbits in Singapore Zoo. To feed them, Zookeeper bought $n$ carrots with lengths $a_1, a_2, a_3, \ldots, 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 \leq n \leq k \leq 10^5)$: the initial number of carrots and the number of rabbits.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 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$.

Difficulty: HARD
Tags: Sorting

Data structures

Mathematics

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
def calc(l, n):
	smol = l // n
	tol = l % n
	return smol * smol * n + (2 * smol + 1) * tol
import heapq
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
curr = [1] * n
q = []
for i in range(n):
	v = a[i]
	heapq.heappush(q, (calc(v, 2) - calc(v, 1), i))
out2 = sum([x * x for x in a])
for i in range(k - n):
	(diff, nex) = heapq.heappop(q)
	curr[nex] += 1
	v = a[nex]
	heapq.heappush(q, (calc(v, curr[nex] + 1) - calc(v, curr[nex]), nex))
	out2 += diff
out = 0
for i in range(n):
	out += calc(a[i], curr[i])
assert out == out2
print(out)


import sys
from heapq import heapify, heappush, heappop

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c for j in range(b)] for i in range(a)]

def list3d(a, b, c, d):
	return [[[d for k in range(c)] for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)
(N, K) = MAP()
A = LIST()

def calc(a, cnt):
	(d, m) = divmod(a, cnt)
	return d ** 2 * (cnt - m) + (d + 1) ** 2 * m
que = []
for a in A:
	que.append((calc(a, 2) - calc(a, 1), 1, a))
heapify(que)
for _ in range(K - N):
	(val, cnt, a) = heappop(que)
	heappush(que, (calc(a, cnt + 2) - calc(a, cnt + 1), cnt + 1, a))
ans = 0
for (_, cnt, a) in que:
	ans += calc(a, cnt)
print(ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = 10 ** 9 + 7

def cal(l, p):
	return l // p * (l // p) * (p - l % p) + (l // p + 1) * (l // p + 1) * (l % p)
(n, k) = mdata()
a = mdata()
ans = 0
H = []
for i in range(n):
	ans += a[i] * a[i]
	heappush(H, (-cal(a[i], 1) + cal(a[i], 2), a[i], 2))
for i in range(k - n):
	temp = heappop(H)
	ans += temp[0]
	heappush(H, (-cal(temp[1], temp[2]) + cal(temp[1], temp[2] + 1), temp[1], temp[2] + 1))
out(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def sq(L, cuts):
	q = L // (cuts + 1)
	r = L % (cuts + 1)
	sq1 = r * pow(q + 1, 2)
	sq2 = (cuts + 1 - r) * pow(q, 2)
	return sq1 + sq2

def gain(L, cuts):
	if cuts == L - 1:
		return 0
	return sq(L, cuts) - sq(L, cuts + 1)

def solve():
	(N, K) = getInts()
	A = getInts()
	queue = []
	h.heapify(queue)
	for a in A:
		cuts = 0
		g = gain(a, 0)
		h.heappush(queue, (-g, a, cuts))
	while K > N:
		K -= 1
		(g, a, cuts) = h.heappop(queue)
		cuts += 1
		g = gain(a, cuts)
		h.heappush(queue, (-g, a, cuts))
	ans = 0
	for (g, a, cuts) in queue:
		ans += sq(a, cuts)
	return ans
print(solve())


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heapify, heappop, heappush

def getCost(num, k):
	part = num // k
	big = num % k
	small = k - big
	return small * part * part + big * (part + 1) * (part + 1)
(n, k) = map(int, input().split())
ls = list(map(int, input().split()))
ar = []
ans = 0
for i in range(n):
	ans += ls[i] * ls[i]
	diff = getCost(ls[i], 1) - getCost(ls[i], 2)
	ar.append([-diff, ls[i], 1])
heapify(ar)
i = 0
while i < k - n:
	elem = heappop(ar)
	ans -= -elem[0]
	nxt = [-1 * (getCost(elem[1], elem[2] + 1) - getCost(elem[1], elem[2] + 2)), elem[1], elem[2] + 1]
	heappush(ar, nxt)
	i += 1
print(ans)


import heapq

def calc(l, n):
	div = l // n
	mod = l % n
	return div * div * n + (2 * div + 1) * mod
(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
cur = [1] * n
heap = []
for i in range(n):
	v = a[i]
	heapq.heappush(heap, (calc(v, 2) - calc(v, 1), i))
ans = 0
for i in range(k - n):
	(_, best) = heapq.heappop(heap)
	cur[best] += 1
	cuts = cur[best]
	heapq.heappush(heap, (calc(a[best], cuts + 1) - calc(a[best], cuts), best))
for i in range(n):
	ans += calc(a[i], cur[i])
print(ans)


import os
import sys
from io import BytesIO, IOBase
import heapq
MOD = 10 ** 5 + 1

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	target = max((sum(a) + (k - 1)) // k - 100, 1)
	cost = []
	currentSplit = []
	currentCost = []
	for elem in a:
		currentSplit.append((elem + target - 1) // target)
		currentCost.append((elem // currentSplit[-1]) ** 2 * currentSplit[-1])
		currentCost[-1] += elem % currentSplit[-1] * (1 + 2 * (elem // currentSplit[-1]))
		if currentSplit[-1] != 1:
			newSplit = currentSplit[-1] - 1
			curDecCost = (elem // newSplit) ** 2 * newSplit
			curDecCost += elem % newSplit * (1 + 2 * (elem // newSplit))
			heapq.heappush(cost, (curDecCost - currentCost[-1]) * MOD + len(currentCost) - 1)
	curAns = sum(currentSplit)
	curCost = sum(currentCost)
	while curAns > k:
		curAns -= 1
		curElem = heapq.heappop(cost)
		addedCost = curElem // MOD
		loc = curElem % MOD
		currentCost[loc] += addedCost
		curCost += addedCost
		currentSplit[loc] -= 1
		if currentSplit[loc] != 1:
			newSplit = currentSplit[loc] - 1
			elem = a[loc]
			curDecCost = (elem // newSplit) ** 2 * newSplit
			curDecCost += elem % newSplit * (1 + 2 * (elem // newSplit))
			heapq.heappush(cost, (curDecCost - currentCost[loc]) * MOD + loc)
	print(curCost)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq

def value(l, parts):
	len1 = l // parts
	len2 = len1 + 1
	cnt2 = l % parts
	cnt1 = parts - cnt2
	return cnt1 * len1 * len1 + cnt2 * len2 * len2

def solve(n, k, a):
	total = 0
	pq = []
	for i in range(n):
		total += a[i] * a[i]
		heapq.heappush(pq, (-1 * value(a[i], 1) + value(a[i], 2), a[i], 2))
	for i in range(k - n):
		temp = heapq.heappop(pq)
		total += temp[0]
		(a, b) = (temp[1], temp[2])
		heapq.heappush(pq, (-value(a, b) + value(a, b + 1), a, b + 1))
	return total
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
print(solve(n, k, a))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from heapq import *
(n, k) = RL()
a = RLL()
heap = []
dic = [[l, l ** 2, (l >> 1) ** 2 * 2 if l & 1 == 0 else (l >> 1) ** 2 + (l + 1 >> 1) ** 2, 2] for l in a]
for i in range(n):
	heap.append((dic[i][2] - dic[i][1], i))
heapify(heap)
for _ in range(k - n):
	(_, i) = heap[0]
	dic[i][3] += 1
	(l, p) = (dic[i][0], dic[i][3])
	(r, ll) = (l % p, l // p)
	t = (p - r) * ll ** 2 + r * (ll + 1) ** 2
	(dic[i][1], dic[i][2]) = (dic[i][2], t)
	heapreplace(heap, (dic[i][2] - dic[i][1], i))
print(sum((a[1] for a in dic)))


import heapq

def f(length, count):
	(u, v) = divmod(length, count)
	return (count - v) * u ** 2 + v * (u + 1) ** 2

def main():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	res = sum((v ** 2 for v in a))
	b = [(-f(v, 1) + f(v, 2), v, 1) for v in a]
	heapq.heapify(b)
	for i in range(k - n):
		(dif, v, count) = heapq.heappop(b)
		res += dif
		heapq.heappush(b, (-f(v, count + 1) + f(v, count + 2), v, count + 1))
	print(res)
	return
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict
sys.setrecursionlimit(300000)

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
from math import factorial as f

def solve():
	(n, k) = sep()
	ar = lis()

	def val(a, b):
		t1 = a % b
		t2 = a // b
		t3 = t2 + 1
		return t1 * (t3 * t3) + (b - t1) * (t2 * t2)
	temp = []
	heapify(temp)
	tot = 0
	for i in ar:
		t = (-(val(i, 1) - val(i, 2)), i, 1)
		tot += i * i
		heappush(temp, t)
	for _ in range(k - n):
		t = heappop(temp)
		(a, b, c) = t
		tot += a
		p = (-(val(b, c + 1) - val(b, c + 2)), b, c + 1)
		heappush(temp, p)
	print(tot)
solve()


import sys
import bisect as bi
import collections as cc
import heapq as hp
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))

def ch(n, k):
	temp = n // k
	still = n % k
	ans = (k - still) * temp ** 2 + still * (temp + 1) ** 2
	return ans
(n, k) = I()
l = I()
ans = 0
heap = []
for i in range(n):
	ans += l[i] ** 2
	hp.heappush(heap, (-ch(l[i], 1) + ch(l[i], 2), l[i], 2))
for i in range(abs(n - k)):
	now = hp.heappop(heap)
	ans += now[0]
	(x, y) = (now[1], now[2])
	hp.heappush(heap, (-ch(x, y) + ch(x, y + 1), x, y + 1))
print(ans)


import math
import heapq

def score_with(size, cuts):
	if cuts == 0:
		return size ** 2
	sup = math.ceil(size / cuts)
	inf = sup - 1
	mod = size % cuts
	if mod == 0:
		nbsup = cuts
		nbinf = 0
	else:
		nbsup = mod
		nbinf = cuts - mod
	return sup ** 2 * nbsup + inf ** 2 * nbinf

def compute_savings(size, nb_cuts):
	return score_with(size, nb_cuts) - score_with(size, nb_cuts + 1)
(N, K) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
pq = []
score = 0
for el in A:
	score += el ** 2
	savings = compute_savings(el, 1)
	heapq.heappush(pq, (-savings, el, 1))
for i in range(K - N):
	(neg_savings, sz, nb_cuts) = heapq.heappop(pq)
	savings = -neg_savings
	score -= savings
	next_savings = compute_savings(sz, nb_cuts + 1)
	heapq.heappush(pq, (-next_savings, sz, nb_cuts + 1))
print(score)


from sys import stdin
import sys
import heapq
q = []
(n, k) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
x = [1] * n
for ind in range(n):
	s = a[ind] // x[ind]
	rem = a[ind] % x[ind]
	score = (s + 1) ** 2 * rem + s ** 2 * (x[ind] - rem)
	s2 = a[ind] // (x[ind] + 1)
	rem2 = a[ind] % (x[ind] + 1)
	score2 = (s2 + 1) ** 2 * rem2 + s2 ** 2 * (x[ind] + 1 - rem2)
	q.append((score2 - score, ind))
heapq.heapify(q)
for loop in range(k - n):
	(tmp, ind) = heapq.heappop(q)
	x[ind] += 1
	s = a[ind] // x[ind]
	rem = a[ind] % x[ind]
	score = (s + 1) ** 2 * rem + s ** 2 * (x[ind] - rem)
	s2 = a[ind] // (x[ind] + 1)
	rem2 = a[ind] % (x[ind] + 1)
	score2 = (s2 + 1) ** 2 * rem2 + s2 ** 2 * (x[ind] + 1 - rem2)
	heapq.heappush(q, (score2 - score, ind))
ans = 0
for i in range(n):
	s = a[i] // x[i]
	rem = a[i] % x[i]
	ans += (s + 1) ** 2 * rem + s ** 2 * (x[i] - rem)
print(ans)


import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
INF = 10 ** 9 + 7

def calc(A, x):
	if A < x:
		return INF
	(d, r) = divmod(A, x)
	return d * d * x + (2 * d + 1) * r
(N, K) = list(map(int, readline().split()))
A = list(map(int, readline().split()))
Q = [(-calc(a, 1) + calc(a, 2), a, 1) for a in A]
Q.sort()
for _ in range(K - N):
	(dif, a, x) = hpp(Q)
	hp(Q, (-calc(a, x + 1) + calc(a, x + 2), a, x + 1))
ans = 0
for (_, a, x) in Q:
	ans += calc(a, x)
print(ans)


from heapq import *

def find_add(a, k):
	extra = a % k
	return (k - extra) * (a // k) ** 2 + extra * (1 + a // k) ** 2
(n, mx) = map(int, input().split())
lst = list(map(int, input().split()))
a = []
heapify(a)
for i in lst:
	heappush(a, (find_add(i, 2) - find_add(i, 1), i, 1))
total = n
while total != mx:
	(curr_cont, el, k) = heappop(a)
	new = (find_add(el, k + 2) - find_add(el, k + 1), el, k + 1)
	heappush(a, new)
	total += 1
sc = 0
while a:
	(curr_cont, el, k) = heappop(a)
	sc += find_add(el, k)
print(sc)


import os
import math
import statistics
true = True
false = False
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-07
(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):
	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()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cost = sum((k ** 2 for k in a))
	from heapq import heappop, heappush
	queue = []

	def f(x, k):
		if k == 1:
			return x ** 2
		if k >= x:
			return x
		k1 = x % k
		k2 = k - k1
		p = x // k
		return k1 * (p + 1) ** 2 + k2 * p ** 2
	for i in a:
		heappush(queue, [-f(i, 1) + f(i, 2), i, 1])
	for i in range(k - n):
		(dec, value, kk) = heappop(queue)
		cost += dec
		kk += 1
		heappush(queue, [-f(value, kk) + f(value, kk + 1), value, kk])
	print(cost)


import heapq

def sum_sqaure(a, k):
	(q, r) = divmod(a, k)
	return q ** 2 * (k - r) + (q + 1) ** 2 * r

def diff(a, k):
	return sum_sqaure(a, k + 1) - sum_sqaure(a, k)
(n, k) = map(int, input().split())
nums = list(map(int, input().split()))
curr = sum((sum_sqaure(a, 1) for a in nums))
Q = [(diff(a, 1), a, 1) for a in nums]
heapq.heapify(Q)
for __ in range(k - n):
	(d, a, i) = heapq.heappop(Q)
	curr += d
	heapq.heappush(Q, (diff(a, i + 1), a, i + 1))
print(curr)


import sys
from heapq import heapify, heapreplace
(n, k, *aaa) = map(int, sys.stdin.buffer.read().split())
ans = 0
hq = []
for a in aaa:
	ans += a * a
for a in aaa:
	p = 1
	(d, m) = divmod(a, p + 1)
	cost = d * d * (p + 1 - m) + (d + 1) * (d + 1) * m
	hq.append((cost - a * a, a * a, a, p))
heapify(hq)
for _ in range(k - n):
	(dec, cur, a, p) = hq[0]
	ans += dec
	cur += dec
	p += 1
	(d, m) = divmod(a, p + 1)
	cost = d * d * (p + 1 - m) + (d + 1) * (d + 1) * m
	heapreplace(hq, (cost - cur, cur, a, p))
print(ans)


from sys import stdin
from heapq import heappush as push, heappop as pop, heapify
(n, k) = map(int, stdin.readline().split())
q = [int(x) for x in stdin.readline().split()]

def f(l, p):
	base = l // p
	leftover = l - base * p
	return (p - leftover) * base * base + leftover * (base + 1) * (base + 1)
carrots = []
for carrot in q:
	push(carrots, (-(f(carrot, 1) - f(carrot, 2)), carrot, 1))
for _ in range(k - n):
	tmp = pop(carrots)
	carrot = tmp[1]
	cuts = tmp[2] + 1
	push(carrots, (-(f(carrot, cuts) - f(carrot, cuts + 1)), carrot, cuts))
print(sum((f(y, z) for (x, y, z) in carrots)))


from sys import stdin, gettrace
from heapq import heappush, heappop
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def cost(ln, pieces):
	extras = ln % pieces
	return ln // pieces * (ln // pieces) * pieces + 2 * (ln // pieces) * extras + extras

def cost_decrease(ln, pieces):
	return cost(ln, pieces) - cost(ln, pieces + 1)

def main():
	(n, k) = map(int, inputi().split())
	aa = [int(a) for a in inputi().split()]
	hp = []
	for a in aa:
		heappush(hp, (-cost_decrease(a, 1), a, 1))
	for _ in range(n, k):
		(_, a, c) = heappop(hp)
		heappush(hp, (-cost_decrease(a, c + 1), a, c + 1))
	print(sum((cost(a, c) for (_, a, c) in hp)))
main()


from heapq import *
(n, k) = map(int, input().split(' '))
ls = []
a = list(map(int, input().split(' ')))
tot = 0

def fun(l, nums):
	std = l // nums
	ext = l - std * nums
	return (nums - ext) * std ** 2 + ext * (std + 1) ** 2
for i in range(n):
	tot += a[i] ** 2
	heappush(ls, (-fun(a[i], 1) + fun(a[i], 2), a[i], 2))
for i in range(k - n):
	temp = heappop(ls)
	tot += temp[0]
	x = temp[1]
	y = temp[2]
	heappush(ls, (-fun(x, y) + fun(x, y + 1), x, y + 1))
print(tot)


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def distribute(n, person, min, max, mode='even'):
	if person == 0 and n == 0:
		return []
	elif not min * person <= n <= max * person:
		return None
	elif mode == 'even':
		(q, m) = divmod(n, person)
		if m == 0:
			return [[q, person]]
		else:
			return [[q, person - m], [q + 1, m]]
	elif mode == 'greedy':
		if max == min:
			return [[max, person]]
		n -= min * person
		(q, m) = divmod(n, max - min)
		if m == 0:
			return [[min, person - q], [max, q]]
		else:
			return [[min, person - 1 - q], [min + m, 1], [max, q]]
	else:
		raise ValueError("'mode' must be 'even' or 'greedy'.")
from heapq import heappop, heapify, heappush
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
q = []
for a in A:
	o1 = a * a - (a // 2) ** 2 - ((a + 1) // 2) ** 2
	o2 = a
	if a != 1:
		q.append(-(o1 << 40 | 2 << 20 | o2))
mask = (1 << 20) - 1
ans = sum((a * a for a in A))
heapify(q)
for _ in range(K - N):
	p = -heappop(q)
	(gain, n, a) = (p >> 40, p >> 20 & mask, p & mask)
	ans -= gain
	if n >= a:
		continue
	distr_new = distribute(a, n + 1, 1, a)
	distr_old = distribute(a, n, 1, a)
	gain = 0
	for (q_, n_) in distr_new:
		gain -= q_ * q_ * n_
	for (q_, n_) in distr_old:
		gain += q_ * q_ * n_
	p = -(gain << 40 | n + 1 << 20 | a)
	heappush(q, p)
print(ans)


import heapq

def cost(L, m):
	min_len = L // m
	rem = L - min_len * m
	return (m - rem) * min_len * min_len + rem * (min_len + 1) * (min_len + 1)

def solve(a, n, k):
	pq = []
	total = 0
	for c in a:
		total += c * c
		decrease_in_cost = cost(c, 1) - cost(c, 2)
		pq.append((-decrease_in_cost, c, 2))
	heapq.heapify(pq)
	for _ in range(k - n):
		top = heapq.heappop(pq)
		total += top[0]
		(c, m) = (top[1], top[2])
		decrease_in_cost = cost(c, m) - cost(c, m + 1)
		heapq.heappush(pq, (-decrease_in_cost, c, m + 1))
	return total
(n, k) = (int(x) for x in input().split())
a = list((int(x) for x in input().split()))
print(solve(a, n, k))


import sys
input = sys.stdin.readline
import heapq
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
score = n
ANS = 0
for a in A:
	ANS += a ** 2

def calc(x, sc):
	if sc == x:
		return x
	if sc > x:
		return 1 << 60
	(r, q) = divmod(x, sc)
	return (sc - q) * r ** 2 + q * (r + 1) ** 2
X = []
for a in A:
	now = a ** 2
	net = calc(a, 2)
	X.append((net - now, a, 2))
heapq.heapify(X)
for i in range(k - score):
	(sa, a, sc) = heapq.heappop(X)
	ANS += sa
	now = calc(a, sc)
	net = calc(a, sc + 1)
	heapq.heappush(X, (net - now, a, sc + 1))
print(ANS)


from heapq import *
(n, k) = map(int, input().split(' '))

def val(l, nums):
	unit = l // nums
	extra = l - unit * nums
	return (nums - extra) * unit * unit + extra * (unit + 1) * (unit + 1)
pq = []
arr = list(map(int, input().split(' ')))
total = 0
for x in range(n):
	total += arr[x] * arr[x]
	heappush(pq, (-val(arr[x], 1) + val(arr[x], 2), arr[x], 2))
for x in range(k - n):
	temp = heappop(pq)
	total += temp[0]
	(a, b) = (temp[1], temp[2])
	heappush(pq, (-val(a, b) + val(a, b + 1), a, b + 1))
print(total)


from bisect import *
from collections import *
from math import *
from heapq import *
from typing import List
from itertools import *
from operator import *
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

@lru_cache(None)
def fact(x):
	if x < 2:
		return 1
	return fact(x - 1) * x

@lru_cache(None)
def per(i, j):
	return fact(i) // fact(i - j)

@lru_cache(None)
def com(i, j):
	return per(i, j) // fact(j)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d
(n, k) = RL()
a = RLL()
heap = []
ans = 0

def val(x, k):
	(a, b) = divmod(x, k)
	return (a + 1) ** 2 * b + a ** 2 * (k - b)
for i in range(n):
	ans += a[i] ** 2
	cur = -val(a[i], 1) + val(a[i], 2)
	heappush(heap, (cur, a[i], 1))
k -= n
for i in range(k):
	(cur, m, n) = heappop(heap)
	ans += cur
	cur = -val(m, n + 1) + val(m, n + 2)
	heappush(heap, (cur, m, n + 1))
print(ans)


(n, k) = map(int, input().split())
a = [*map(int, input().split())]
import heapq

def cut(i, k):
	t = (i + k - 1) // k
	amt = i % k
	if amt == 0:
		amt = k
	return amt * t ** 2 + (k - amt) * (t - 1) ** 2
h = []
for x in a:
	heapq.heappush(h, (cut(x, 2) - cut(x, 1), x, 1))
for _ in range(k - len(a)):
	(_, y, z) = heapq.heappop(h)
	heapq.heappush(h, (cut(y, z + 2) - cut(y, z + 1), y, z + 1))
print(sum((cut(y, z) for (x, y, z) in h)))


import heapq

def time(l, p):
	(q, r) = divmod(l, p)
	return (p - r) * q ** 2 + r * (q + 1) ** 2

def f(l, p):
	return time(l, p + 1) - time(l, p)
(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
splits = [1] * n
queue = [(f(a_i, splits[i]), i) for (i, a_i) in enumerate(a)]
heapq.heapify(queue)
total = sum((a_i * a_i for a_i in a))
for _ in range(k - n):
	(f_i, i) = heapq.heappop(queue)
	splits[i] += 1
	total += f_i
	heapq.heappush(queue, (f(a[i], splits[i]), i))
print(total)


import os
import sys
from io import BytesIO, IOBase
from heapq import heappush, heappop

def val(L, P):
	if L <= P:
		return L
	(q, r) = divmod(L, P)
	return q * q * (P - r) + (q + 1) * (q + 1) * r

def main():
	(n, k) = getints()
	a = getints()
	pq = []
	cost = 0
	for x in a:
		now = val(x, 1)
		nxt = val(x, 2)
		cost += now
		if nxt < now:
			heappush(pq, (nxt - now, now, x, 2))
	for _ in range(k - n):
		(impr, now, L, P) = heappop(pq)
		now += impr
		cost += impr
		nxt = val(L, P + 1)
		if nxt < now:
			heappush(pq, (nxt - now, now, L, P + 1))
	print(cost)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
main()


from heapq import heapify, heappop, heappush

def getCost(num, k):
	part = num // k
	big = num % k
	small = k - big
	return small * part * part + big * (part + 1) * (part + 1)
(n, k) = map(int, input().split())
ls = list(map(int, input().split()))
ar = []
ans = 0
for i in range(n):
	ans += ls[i] * ls[i]
	diff = getCost(ls[i], 1) - getCost(ls[i], 2)
	ar.append([-diff, ls[i], 1])
heapify(ar)
i = 0
while i < k - n:
	elem = heappop(ar)
	ans -= -elem[0]
	nxt = [-1 * (getCost(elem[1], elem[2] + 1) - getCost(elem[1], elem[2] + 2)), elem[1], elem[2] + 1]
	heappush(ar, nxt)
	i += 1
print(ans)


from heapq import heappush, heappop

def f(length, n_piece):
	width = length // n_piece
	extra = length - width * n_piece
	return width ** 2 * (n_piece - extra) + (width + 1) ** 2 * extra

def solve():
	(N, K) = map(int, input().split())
	A = [int(x) for x in input().split()]
	ans = sum((a ** 2 for a in A))
	heap = []
	for (i, a) in enumerate(A):
		decrease = f(a, 2) - f(a, 1)
		n_piece = 2
		heappush(heap, (decrease, a, n_piece))
	for _ in range(K - N):
		(decrease, a, n_piece) = heappop(heap)
		ans += decrease
		decrease = f(a, n_piece + 1) - f(a, n_piece)
		n_piece = n_piece + 1
		heappush(heap, (decrease, a, n_piece))
	return ans
print(solve())


import heapq
(N, K) = map(int, input().split())
X = list(map(int, input().split()))
Y = [((x // 2) ** 2 + (x // 2 + x % 2) ** 2 - x ** 2, x ** 2, 1, x) for x in X]
l = []
for x in Y:
	heapq.heappush(l, x)
R = 0
for _ in range(K - N):
	(t, x, y, s) = heapq.heappop(l)
	nx = x + t
	y += 1
	(k, m) = divmod(s, y + 1)
	nt = (y + 1 - m) * k ** 2 + m * (k + 1) ** 2 - nx
	heapq.heappush(l, (nt, nx, y, s))
R = 0
for (t, x, y, s) in l:
	R += x
print(R)


import heapq

def f(x, c):
	return x % c * (x // c + 1) ** 2 + (c - x % c) * (x // c) ** 2

def g(x, c):
	return f(x, c) - f(x, c - 1)
(n, k) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
b = [(g(x, 2), 1, x) for x in a]
heapq.heapify(b)
for i in range(k - n):
	y = heapq.heappop(b)
	y = (g(y[2], y[1] + 2), y[1] + 1, y[2])
	heapq.heappush(b, y)
c = 0
for z in b:
	c += f(z[2], z[1])
print(c)


import sys
input = sys.stdin.buffer.readline
from heapq import heappush, heappop

def min_val(amt, parts):
	base = amt // parts
	extra = amt % parts
	return extra * (base + 1) ** 2 + (parts - extra) * base ** 2

def prog():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	heap = []
	total_time = 0
	for length in a:
		total_time += length ** 2
		heappush(heap, [min_val(length, 2) - length ** 2, [length, 2]])
	for i in range(k - n):
		curr = heappop(heap)
		total_time += curr[0]
		heappush(heap, [min_val(curr[1][0], curr[1][1] + 1) - min_val(curr[1][0], curr[1][1]), [curr[1][0], curr[1][1] + 1]])
	print(total_time)
prog()


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data

def find(a, left):
	now = a % left * (a // left + 1) ** 2 + (left - a % left) * (a // left) ** 2
	left += 1
	after = a % left * (a // left + 1) ** 2 + (left - a % left) * (a // left) ** 2
	return now - after
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	ans += a[i] ** 2
a = [(-find(a[i], 1), a[i], 1) for i in range(n)]
heapq.heapify(a)
su = n
while su < k:
	(e, t, no) = heapq.heappop(a)
	ans += e
	su += 1
	heapq.heappush(a, (-find(t, no + 1), t, no + 1))
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def help(val, part):
	temp = val // part
	rem = val % part
	return temp * temp * (part - rem) + (temp + 1) * (temp + 1) * rem

def solve(case):
	(n, k) = sep()
	a = lis()
	curr = 0
	for i in range(n):
		curr += a[i] * a[i]
	h = []
	parts = [1] * n
	for i in range(n):
		heappush(h, (help(a[i], 2) - help(a[i], 1), i))
	cnt = n
	while cnt < k:
		temp = heappop(h)
		(diff, ele) = (temp[0], temp[1])
		curr += diff
		parts[ele] += 1
		heappush(h, (help(a[ele], parts[ele] + 1) - help(a[ele], parts[ele]), ele))
		cnt += 1
	print(curr)
testcase(1)


import heapq
(n, k) = map(int, input().split())
A = list(map(int, input().split()))

def cal(x, m):
	(k, r) = divmod(x, m)
	return r * (k + 1) ** 2 + (m - r) * k ** 2
hp = [(cal(a, 2) - cal(a, 1), a, 2) for a in A]
heapq.heapify(hp)
ans = sum((a ** 2 for a in A))
for _ in range(k - n):
	(d, x, m) = heapq.heappop(hp)
	ans += d
	heapq.heappush(hp, (cal(x, m + 1) - cal(x, m), x, m + 1))
print(ans)


from sys import stdin
input = stdin.readline

def A():
	t = int(input())
	for _ in range(t):
		(x1, y1, x2, y2) = map(int, input().split())
		if x2 == x1:
			print(abs(y2 - y1))
		elif y1 == y2:
			print(abs(x2 - x1))
		else:
			print(abs(x2 - x1) + abs(y2 - y1) + 2)

def B():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = list(input().rstrip())
		(rl, ll, lr, rr) = (0, 0, 0, 0)
		(lcount, rcount) = (0, 0)
		for i in range(0, n - 1):
			if s[i] == '<':
				if s[i + 1] == '>':
					lr += 1
				elif s[i + 1] == '<':
					ll += 1
				lcount += 1
			elif s[i] == '>':
				if s[i + 1] == '>':
					rr += 1
				elif s[i + 1] == '<':
					rl += 1
				rcount += 1
		if s[n - 1] == '<':
			if s[0] == '<':
				ll += 1
			elif s[0] == '>':
				lr += 1
			lcount += 1
		elif s[n - 1] == '>':
			if s[0] == '<':
				rl += 1
			elif s[0] == '>':
				rr += 1
			rcount += 1
		if lcount == 0 or rcount == 0:
			print(n)
		else:
			print(n - ll - lr - rl - rr)

def C():
	t = int(input())
	for _ in range(t):
		s = list(input().rstrip())
		n = len(s)
		i = 0
		remaining = 0
		depth = 0
		j = n - 1
		while j >= i:
			if s[j] == 'A':
				depth += 1
				if depth > 0:
					remaining += 1
					depth = 0
			else:
				depth -= 1
			j -= 1
		remaining += depth % 2
		print(remaining)

def D():
	from collections import deque
	n = int(input())
	a = list(map(int, input().split()))
	cols = [[]] * n
	filledCols = deque()
	k = n - 1
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			cols[i] = [k]
			filledCols.appendleft(i)
			k -= 1
	filled23Cols = deque()
	for i in range(n - 1, -1, -1):
		if a[i] == 2:
			if len(filledCols) == 0 or filledCols[-1] < i:
				print('-1')
				return
			cols[i] = [cols[filledCols.pop()][0]]
			filled23Cols.append(i)
		elif a[i] == 3:
			if (len(filledCols) == 0 or filledCols[-1] < i) and len(filled23Cols) == 0:
				print('-1')
				return
			cols[i] = [k]
			if len(filled23Cols) > 0:
				cols[filled23Cols.pop()].append(k)
			else:
				cols[filledCols.pop()].append(k)
			filled23Cols.append(i)
			k -= 1
	tot = 0
	for i in cols:
		tot += len(i)
	print(tot)
	for i in range(len(cols)):
		if len(cols[i]) > 0:
			for j in cols[i]:
				print(j + 1, i + 1)

def E():

	def f(orig, div):
		return (div - orig % div) * (orig // div) ** 2 + orig % div * (orig // div + 1) ** 2
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	from math import ceil
	avgSize = sum(a) / k
	rem = []
	tot = 0
	k -= n
	for i in a:
		tot += i ** 2
		if i > avgSize:
			rem.append(i)
	l = len(rem)
	divs = [[rem[i] ** 2] for i in range(l)]
	for i in range(len(rem)):
		j = 2
		while rem[i] / j >= avgSize:
			divs[i].append(f(rem[i], j))
			j += 1
		divs[i].append(f(rem[i], j))
	x = []
	for i in divs:
		for j in range(1, len(i)):
			x.append(abs(i[j] - i[j - 1]))
	x.sort(reverse=True)
	print(tot - sum(x[0:k]))
E()


import heapq
import sys
input = iter(sys.stdin.read().splitlines()).__next__

def time(l, p):
	rounded_up = l % p
	rounded_down = p - rounded_up
	return rounded_down * (l // p) ** 2 + rounded_up * (l // p + 1) ** 2

def f(l, p):
	return time(l, p + 1) - time(l, p)
(n, k) = map(int, input().split())
a = [int(i) for i in input().split()]
splits = [1] * n
queue = [(f(a_i, splits[i]), i) for (i, a_i) in enumerate(a)]
heapq.heapify(queue)
total = sum((a_i * a_i for a_i in a))
for _ in range(k - n):
	(f_i, i) = heapq.heappop(queue)
	splits[i] += 1
	total += f_i
	heapq.heappush(queue, (f(a[i], splits[i]), i))
print(total)


from sys import stdin, stdout
from heapq import heappush, heappop

def calc(x, y):
	a = x // y
	l = x - y * a
	r = a * a * (y - l) + (a + 1) * (a + 1) * l
	return r
(n, k) = map(int, stdin.readline().split())
a_a = list(map(int, stdin.readline().split()))
res = 0
hpa = []
for i in range(n):
	res += a_a[i] * a_a[i]
	heappush(hpa, [calc(a_a[i], 2) - calc(a_a[i], 1), 2, i])
for i in range(k - n):
	m_a = heappop(hpa)
	res += m_a[0]
	heappush(hpa, [calc(a_a[m_a[2]], m_a[1] + 1) - calc(a_a[m_a[2]], m_a[1]), m_a[1] + 1, m_a[2]])
stdout.write(str(res))


from heapq import *
Z = lambda : map(int, input().split())
V = lambda n, k: n % k * (n // k + 1) ** 2 + (k - n % k) * (n // k) ** 2
D = lambda n, k: V(n, k) - V(n, k + 1)
(n, k) = Z()
w = k - n + 1
N = n * w
a = [*Z()]
s = sum((i * i for i in a))
d = 0
b = [-D(a[i], 1) * N - i for i in range(n)]
heapify(b)
for i in range(w - 1):
	v = -heappop(b)
	d += v // N
	i = v % n
	l = v // n % w
	heappush(b, -D(a[i], l + 2) * N - (l + 1) * n - i)
print(s - d)


import os, sys
from io import BytesIO, IOBase
from heapq import *

class Node:

	def __init__(self, ori, piece):
		self.ori = ori
		self.piece = piece
		self.inc = 0

	def __lt__(self, other):
		return self.inc > other.inc

def main():
	(n, k) = map(int, input().split())
	x = list(map(lambda y: Node(int(y), 1), input().split()))
	for i in x:
		(xx, yy) = divmod(i.ori, i.piece)
		(xx1, yy1) = divmod(i.ori, i.piece + 1)
		aa = i.piece * xx ** 2 + yy * (2 * xx + 1)
		bb = (i.piece + 1) * xx1 ** 2 + yy1 * (2 * xx1 + 1)
		i.inc = aa - bb
	heapify(x)
	for _ in range(k - n):
		r = heappop(x)
		r.piece += 1
		(xx, yy) = divmod(r.ori, r.piece)
		aa = r.piece * xx ** 2 + yy * (2 * xx + 1)
		(xx1, yy1) = divmod(r.ori, r.piece + 1)
		bb = (r.piece + 1) * xx1 ** 2 + yy1 * (2 * xx1 + 1)
		r.inc = aa - bb
		heappush(x, r)
	ti = 0
	for j in x:
		(rr, rr1) = divmod(j.ori, j.piece)
		ti += j.piece * rr * rr + (2 * rr + 1) * rr1
	print(ti)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from math import inf
from heapq import heapify, heappush, heappop

def make_heap_item(a, new_pieces_n):
	weight = take_min_final_sum(a, new_pieces_n - 1) - take_min_final_sum(a, new_pieces_n)
	return (-weight, a, new_pieces_n)

def take_min_final_sum(a, pieces_n):
	if a < pieces_n:
		return +inf
	(lower_term, higher_term_n) = divmod(a, pieces_n)
	higher_term = lower_term + 1
	lower_term_n = pieces_n - higher_term_n
	return lower_term ** 2 * lower_term_n + higher_term ** 2 * higher_term_n

def read_ints():
	return map(int, input().split())
(n, k) = read_ints()
a_seq = tuple(read_ints())
best_new_maxs = [make_heap_item(a, 2) for a in a_seq]
heapify(best_new_maxs)
for i in range(k - n):
	(neg_best_new_max, initial_value, pieces_n) = heappop(best_new_maxs)
	pieces_n += 1
	new_item = make_heap_item(initial_value, pieces_n)
	heappush(best_new_maxs, new_item)
result = sum((take_min_final_sum(a, pieces_n_plus_1 - 1) for (_, a, pieces_n_plus_1) in best_new_maxs))
print(result)


from heapq import *
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
count = [0] * n
b = []
for i in range(n):
	x = a[i]
	diff = x ** 2 - ((x // 2) ** 2 + ((x + 1) // 2) ** 2)
	b.append((-diff, i))
heapify(b)
for _ in range(k - n):
	(diff, index) = heappop(b)
	diff *= -1
	c = count[index] + 1
	count[index] = c
	num = a[index]
	c += 1
	now = 0
	rem = num % c
	length = num // c
	now += length ** 2 * (c - rem)
	now += (length + 1) ** 2 * rem
	c += 1
	next = 0
	rem = num % c
	length = num // c
	next += length ** 2 * (c - rem)
	next += (length + 1) ** 2 * rem
	heappush(b, (-abs(now - next), index))
ans = 0
for i in range(n):
	c = count[i] + 1
	num = a[i]
	rem = num % c
	length = num // c
	ans += length ** 2 * (c - rem)
	ans += (length + 1) ** 2 * rem
print(ans)


import sys
from heapq import *
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():

	def val(l, nums):
		unit = l // nums
		extra = l - unit * nums
		return (nums - extra) * pow(unit, 2) + extra * pow(unit + 1, 2)
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	pq = []
	res = 0
	for i in range(n):
		res += pow(A[i], 2)
		heappush(pq, (-val(A[i], 1) + val(A[i], 2), A[i], 2))
	for _ in range(k - n):
		temp = heappop(pq)
		res += temp[0]
		(a, b) = (temp[1], temp[2])
		heappush(pq, (-val(a, b) + val(a, b + 1), a, b + 1))
	print(res)
resolve()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from heapq import heappop, heappush
	input = sys.stdin.readline

	def calc(a, d):
		return (a // d + 1) ** 2 * (a % d) + (a // d) ** 2 * (d - a % d)
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = 0
	pq = []
	for a in A:
		ans += a * a
		if a > 1:
			heappush(pq, (calc(a, 2) - calc(a, 1), a, 2))
	for _ in range(K - N):
		(g, a, d) = heappop(pq)
		ans += g
		if a > d:
			heappush(pq, (calc(a, d + 1) - calc(a, d), a, d + 1))
	print(ans)
main()


from sys import stdin
input = stdin.readline
from heapq import heappush, heappop

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == k:
		print(sum((i ** 2 for i in a)))
		return

	def cal(l, pieces):
		(optimal, extra) = divmod(l, pieces)
		return (pieces - extra) * optimal ** 2 + extra * (optimal + 1) ** 2
	h = []
	for i in a:
		heappush(h, [cal(i, 2) - cal(i, 1), i, 2])
	res = sum((i ** 2 for i in a))
	while n < k:
		n += 1
		(d, l, p) = heappop(h)
		res += d
		heappush(h, [cal(l, p + 1) - cal(l, p), l, p + 1])
	print(res)
solve()