Candy Distribution Minimization

In this problem, there are n children and a package containing m candies. Each child i expects to receive a_i candies. If a child receives fewer than a_i candies, then the child becomes angry, and the anger level is equal to the square of the number of candies missing. In other words, if the child receives x candies (with x < a_i), the anger level is \( (a_i - x)^2 \). Your task is to distribute exactly m candies among the children in such a way that the total anger (i.e. the sum of the anger levels over all children) is minimized.

Note: If a child receives at least a_i candies, his anger level is 0. It is guaranteed that \( m < \sum_{i=1}^{n} a_i \), so it is impossible to completely satisfy every child's expectation.

Mathematical Formulation:

Let \( x_i \) be the number of candies given to child \( i \) (an integer such that \( 0 \le x_i \le a_i \)). We must have:

[ \sum_{i=1}^{n} x_i = m ]

The anger level for child \( i \) is defined as:

[ \text{anger}_i = \begin{cases} (a_i - x_i)^2, & \text{if } x_i < a_i,\ 0, & \text{if } x_i \ge a_i. \end{cases} ]

The objective is to minimize:

[ \sum_{i=1}^{n} (a_i - x_i)^2. ]

Hint: Consider redefining \( d_i = a_i - x_i \). Then the constraint becomes \( \sum_{i=1}^{n} d_i = \sum_{i=1}^{n} a_i - m \) with \( 0 \le d_i \le a_i \), and the goal is to minimize \( \sum_{i=1}^{n} d_i^2 \). Since the penalty is convex, the minimum is achieved when the \( d_i \)'s are as equal as possible, subject to the individual upper bounds \( a_i \).

inputFormat

The first line contains two integers \( n \) and \( m \) separated by a space.

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \) separated by spaces, where \( a_i \) is the expected number of candies for the \( i\textsuperscript{th} \) child.

Constraints:

• \( 1 \le n \le 10^5 \)
• \( 0 \le m < \sum_{i=1}^{n} a_i \)
• \( 1 \le a_i \le 10^9 \)

outputFormat

Output a single integer, the minimum possible total anger, i.e. the minimal value of \( \sum_{i=1}^{n} (a_i - x_i)^2 \) achievable by an optimal distribution.

sample

3 5
3 4 5

17