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 heapq


def cost(L, m):
    """Min cost (time) of cutting L into m pieces.
    L = p1^2+...+pm^2, L is minimized when cutting as evenly as possible.
    """
    min_len = L//m
    rem = L-min_len*m
    # "Spread" rem across rem pieces, each receives +1 in len, so we have rem pieces of len `min_len+1` and m-rem pieces of len `min_len`.
    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 by cutting c in 2 pieces (compared to no cut)
        decrease_in_cost = cost(c, 1)-cost(c, 2)
        # Max heap by negating value
        pq.append((-decrease_in_cost, c, 2))

    heapq.heapify(pq)  # heapify modifies pq in-place, returns None!

    # Since we start with n pieces and end with k pieces, so the number of cut is k-n
    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))
        # Why does this work?
        # Note at some point if we find that it's better to cut c in m2 pieces than the current cutting in m1 pieces, cost(c, 1) - cost(c, m1) + cost(c, m1) - cost(c, m2) = cost(c,1) - cost(c,m2).

    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))
