C1LJUTNJ - Ljutnja

no tags 

Children in a kindergarten have received a large sack containing M candies. It has been decided that the candies are to be distributed among N children.

Each child has stated the number of candies that it wants. If a child isn’t given the amount of candy it wants, it will get angry. In fact it’ll get angrier for each candy it is deprived of. Some speculate that its anger will be equal to the square of the number of candies it is deprived of. For instance, if Mirko states that he wants 32 candies but receives only 29, he would be missing 3 candies, so his anger would be equal to 9.

Unfortunately, there is an insufficient amount of candy to satisfy all children. Therefore, the candies should be distributed in such a way that the sum of the children’s anger is minimal.

Input

The first line contains two integers, M (1 ≤ M ≤ 2.109) and N (1 ≤ N ≤ 100 000).

The following N lines contain integers (one per line) which represent the wishes of the children. Those numbers are all strictly less than 2.109, and their sum always exceeds M.

Output

The first and only line of output must contain the minimum sum of the children’s anger.

Note: The test cases will ensure that the result fits in a 64-bit unsigned integer: int64 in Pascal, long long in C/C++, long in Java.

Example

Input:
5 3
1
3
2
Output:
1
Input:
10 4
4
5
2
3
Output:
4

hide comments
praveen dhanuka: 2012-03-05 17:57:24

will O(NlogN + N) is sufficient to cross the limit.........

numerix: 2011-02-18 20:59:51

Whoever-deleted-his-comment: Michael T. is right! You can only get AC, if your code produces a definetely wrong answer. If you check it with a language with bigint support you'll verify this. You have to cut down results to 64-Bit to get AC with such kind of languages.

Michael T: 2011-02-18 15:51:52

@someone-who-deleted-my-comment: Just tried and still the same issue: WA without manual mod64 (at ~9 case).

Michael T: 2011-02-20 05:13:41

Results _do_not_ fit into int64. Tested on official input, where calculated anger "just happens" to be positive in the end in 2 cases (namely 4 and 9). Had issue in python.
Print answer modulo 2**64.

Last edit: 2011-01-28 17:38:08
LeppyR64: 2011-01-03 13:49:28

@madhav your solutionn should have better complexity than that.

madhav: 2011-01-01 07:52:49

would binary search on the required value work?

Fajrin Azis: 2010-12-13 15:14:44

for you that think your algorithm is right but still get WA, change all of your variable to LL, or multiply every int variable with *1LL. i got many WA and then compared it with official solution, the only different was the variable declaration haha, unlucky me.

Last edit: 2010-12-13 15:15:42
Prateek Khandelwal: 2011-05-11 13:35:22

my code is working for the given test cases and many more but then also it is giving wrong answer plz give a different test case...

David Gómez: 2010-11-19 16:17:25

Nice problem!


Added by:Race with time
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:COCI 2010-2011 1-st Round