문제 번호 : 급식에 나온 닭다리

문제 번호 : 급식에 나온 닭다리

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 71  해결 문제 수: 8
[제출][채점상황][게시판][:]

문제 설명

요즘 급식에 닭다리가 자주 나온다. 문제는 학생들이 요구한 닭다리의 개수와 급식에 나오는 닭의 개수가 맞지 않아 학생들의 원성이 하늘을 찌른다.

어떻게 하면 학생들에 공평하게 분배할 것인가에 대한 고민이다. 그리고 문제는 학생들이 자신이 원하는 닭다리 숫자와 배식 받은 숫자의 차이의 제곱만큼의 기분 나쁨을 느낀다는 것이다. 예를 들어, 한 학생이 원하는 닭다리 숫자가 32개이고 배식 받은 닭다리의 숫자가 29개라면 3개의 닭다리가 부족하게 된다. 따라서 기분 나쁨의 정도는 9가 된다.

영양선생님이 고민을 했다. 그러나 뾰족한 해결책이 없다. 그래서 프로그래밍에 능숙한 BJN선생님께 의뢰를 하였다. 어떻게 분배하면 학생들의 기분 나쁨의 정도의 합을 최소화 하는 프로그램을 만들 수 있을까?

급식에 나오는 닭다리수 M, 학생의 수 N이 입력으로 주어지고 각 학생에 따라 요구하는 닭다리수가 순차적으로 입력된다.

입력

첫 줄에 공백으로 두 정수 MN이 순서대로 입력된다. (1<=M<=2*109, 1<=N<=100000).

다음 줄에 N개의 라인에 각 학생들이 요구하는 닭다리 개수가 입력된다. 2*109보다 작고, 그 합은 항상 M을 초과한다.

출력

첫줄에 학생들의 기분 나쁨의 합의 최솟값을 출력한다

입력예시

5 3
1
3
2

출력예시

1

도움말

[제출][채점상황]