В зоопарке Сингапура есть несколько кроликов. Чтобы накормить их, смотритель зоопарка купил \(n\) морковок, имеющих длины \(a_1, a_2, a_3, \ldots, a_n\). Кролики очень быстро размножаются. У смотрителя зоопарка сейчас есть \(k\) кроликов и недостаточно морковок, чтобы прокормить их всех. Чтобы решить эту проблему, он решил разрезать морковки так, чтобы суммарно получилось \(k\) кусков. По некоторой причине длины всех получившихся морковок должны быть положительными целыми числами.
Кролику очень сложно кушать длинную морковку, поэтому время, которое требуется, чтобы съесть морковку длины \(x\), равно \(x^2\).
Помогите смотрителю зоопарка разделить его морковки и найдите минимальное суммарное время, которое потребуется кроликам, чтобы их съесть.
Выходные данные
Выведите одно целое число: минимальное суммарное время, которое потребуется кроликам, чтобы съесть морковки при каком-то их разделении.
Примечание
Для первого теста оптимальные размеры морковок это \(\{1,1,1,2,2,2\}\). Время, которое потребуется, чтобы съесть эти морковки, равно \(1^2+1^2+1^2+2^2+2^2+2^2=15\).
Для второго теста оптимальные размеры морковок это \(\{4,5,5,5\}\). Время, которое потребуется, чтобы съесть эти морковки, равно \(4^2+5^2+5^2+5^2=91\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6
5 3 1
|
15
|
|
2
|
1 4
19
|
91
|