Cookie Distribution Minimizing Grievance

Santa has \(M\) cookies and wants to distribute them among \(N\) children, giving each child at least one cookie. Each child \(i\) has a greed factor \(g_i\). If there are \(a_i\) children receiving strictly more cookies than child \(i\), then child \(i\) feels a grievance of \(g_i \times a_i\). Santa wants to assign cookies in a way that minimizes the total grievance of all children.

Distribution Strategy:

Let \(x = \lfloor M/N \rfloor\) and \(r = M \bmod N\). Ideally, if we give \(r\) children one extra cookie, then:

• \(r\) children receive \(x+1\) cookies.
• The remaining \(N - r\) children receive \(x\) cookies.

In such an arrangement, each child receiving \(x\) cookies has \(a_i = r\) (since there are exactly \(r\) children who get \(x+1\) cookies) and those receiving \(x+1\) cookies have \(a_i = 0\). The total grievance is \(r \times \sum_{\text{child } i \text{ with } x \text{ cookies}} g_i\).

To minimize the total, we should assign the extra cookie to the children with the highest greed factors so that the sum of greed values among children with \(x\) cookies is as small as possible. Your task is to compute the minimum total grievance following this optimal strategy.

inputFormat

The first line contains two integers \(N\) and \(M\) (with \(M \ge N\)).

The second line contains \(N\) integers: \(g_1, g_2, \dots, g_N\), where \(g_i\) is the greed factor of the \(i\)-th child.

outputFormat

Output a single integer representing the minimum possible total grievance.

sample

3 4
1 2 3

3