Задача Presents. Діти в дитячому садку отримали великий мішок з цукерками. Їх у мішку М штук. Вирішено, що цукерки повинні бути розподілені серед N дітей. Кожна дитина вказала кількість цукерок, які вона хоче. Якщо дитині не дістанеться та кількість цукерок, яку вона хоче, віна буде ображена. «Гнів» буде рівним квадрату кількості бажаних, але не отриманих цукерок. Наприклад, якщо Василько стверджує, що хоче 32 цукерки, але отримує лише 29, йому не вистачає 3 цукерок, тому його «гнів» буде рівним 9. Допоможіть розподілити цукерки так, щоб сума дитячого гніву була мінімальною.
Технічні умови. Програма Presents читає з пристрою стандартного введення в першому рядку два цілих числа M (1 ≤ M ≤ 2 · 109) і N (1 ≤ N ≤ 100 000), наступні N рядків містять цілі числа (по одній на рядок), які відображають побажання дітей. Ці числа строго менші 2 · 109, і їх сума завжди перевищує М. Програма виводить єдине шукане число – мінімально можливу сумі дитячого «гніву».
Приклади.
|
Введення |
Виведення |
|
5 3 1 3 2 |
1 |
| Введення | Виведення |
|
10 4 4 5 2 3 |
4 |