Candy Candy

Time limit1sMemory limit128 MB

Summary

Distribute M candies among N friends to minimize the sum of squared shortages, using a binary-search-on-marginal-cost style allocation strategy.

Level: Medium7 of 10
Topics: Binary search, Greedy, Math
Solved: No attempts yet

Problem

Taekhee received a box containing M candies. He wants to distribute these candies among N friends.

Each friend sent the number of candies they would like to receive. If a friend receives fewer candies than requested, the number of candies they did not receive is that friend's shortage. The friend's anger value is the square of the shortage.

For example, if a friend wanted 32 candies but received 29, the shortage is 3 and the anger value is 3^2 = 9.

Given the number of candies Taekhee has, the number of friends, and each friend's requested amount, distribute the candies so that the sum of all anger values is minimized. Output that minimum value.

Input

The first line contains the number of candies M (1 ≤ M ≤ 2×10^9) and the number of friends N (1 ≤ N ≤ 100,000).

Each of the next N lines contains one friend's requested number of candies. Each requested amount is less than 2×10^9. The total requested amount is always greater than M.

Output

Output the minimum possible sum of the friends' anger values, modulo 2^64.

Examples2

Example 1
Input
```
5 3
1
3
2
```
Expected output
```
1
```
Example 2
Input
```
10 4
4
5
2
3
```
Expected output
```
4
```