시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 7 3 (43%) 3
문제
숲속유치원에 다니는 어린이들은 $M$개의 사탕이 담긴 큰 가방을 받았다. 이 유치원에는 $N$명의 어린이가 있는데, 이 사탕들을 분배하기로 결정했다. 각 어린이들은 자신들이 원하는 사탕의 숫자를 말하기 시작했는데, 원하는 만큼 받지 못한다면 그 어린이는 화를 낼 것이다. 더 자세히 말하면, 어린이들이 화내는 것을 수치로 표현할 수 있는데, 부족한 사탕의 수의 제곱만큼 화를 내게 된다. 예를 들어, 수정이는 32개의 사탕을 받고 싶었지만 29개만 받은 경우, 3개를 덜 받았기 떄문에 9만큼 화를 내게 된다. 당연하지만, 불행히도 모든 어린이를 만족시킬만큼 사탕이 충분하지 않다. 그래서, 어린이들이 화를 내는 양의 합을 최소로 하는 방법으로 사탕을 나눠주려고 한다.
입력
첫 번째 줄에 가방에 담긴 사탕의 수 $M$과 유치원에 다니는 어린이의 수 $N$이 주어진다. $(1 \le M \le 2 \times 10^9, 1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에 걸쳐 각 어린이가 원하는 사탕의 수가 주어진다. 이 사탕의 수는 $2 \times 10^9$ 이하이고, 모든 어린이가 원하는 사탕의 수의 합은 항상 $M$을 초과한다.
출력
사탕을 나눠줬을 때, 어린이들이 화를 내는 양의 합의 최소값을 출력한다. 이 때, 답은 항상 64비트 부호 없는 정수형으로 표현 가능하다.
힌트
#### 채점 40%의 점수에 해당하는 입력 데이터는 $M \le 200\,000$을 만족한다. 70%의 점수에 해당하는 입력 데이터는 각 어린이가 원하는 사탕의 수가 $100\,000$ 이하이다. 80%의 점수에 해당하는 입력 데이터는 $M \le 200\,000$ 이거나 각 어린이가 원하는 사탕의 수가 $100\,000$ 이하이다. #### 예제 입력 1 ``` 5 3 1 3 2 ``` #### 예제 출력 1 ``` 1 ``` #### 예제 입력 2 ``` 10 4 4 5 2 3 ``` #### 예제 출력 2 ``` 4 ```