C1LJUTNJ - Ljutnja
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
asdfs:
2013-11-26 11:49:17
binary search works well :) |
|
Nishant Gupta:
2013-07-22 03:20:11
wrong sorting costed lots of WA ....finally AC...nice one |
|
kunal keshwani:
2013-07-21 18:32:07
good prob.. really liked it!!! |
|
Ghost Of Perdition:
2013-05-22 02:07:55
according to the official contest problems
|
|
Rohil Sinha:
2012-10-08 22:04:52
MOD is supposed to be 2**63 and not 2**64. |
|
ZODI91:
2012-09-24 05:54:26
Math.h library's pow() function cant handle large values.. |
|
Sardar Khan:
2012-09-23 22:28:41
Nice ques!! loved solving it :)) |
|
:D:
2012-05-29 06:23:48
re Zhiang: read other comments.
|
|
Zhiang:
2012-05-28 19:46:57
does the answer fits in 64 bit
|
|
15972125841321:
2012-05-26 15:20:41
my code runs till 8th file then shows wa... can u plz tell tell me where i m failing.. my submission id 7042992 |
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 |