Несколько дней назад вы приобрели новый дом и сейчас планируете провести в нем капитальный ремонт. Так как зимы в вашем регионе могут быть очень суровыми, вам нужно определиться с системой отопления в каждой комнате.
У вас в доме \(n\) комнат. В \(i\)-й комнате вы можете установить не более \(c_i\) радиаторов системы отопления. Каждый радиатор может иметь несколько секций, но стоимость радиатора из \(k\) секций равна \(k^2\) бурлей.
Так как комнаты имеют разные размеры, то вы рассчитали, что на обогрев \(i\)-й комнаты вам понадобится как минимум \(sum_i\) секций суммарно по всем радиаторам.
Для каждой комнаты посчитайте минимально возможную стоимость установки не более \(c_i\) радиаторов и суммарным количеством секций не менее \(sum_i\).
Выходные данные
Для каждой комнаты выведите одно число — минимально возможная стоимость установки не более \(c_i\) радиаторов с суммарным количеством секций не менее, чем \(sum_i\).
Примечание
В первой комнате, вы можете установить только один радиатор, а потому выгодно приобрести радиатор с \(sum_1\) секциями. Стоимость радиатора равна \((10^4)^2 = 10^8\).
Во второй комнате вы можете установить вплоть до \(10^4\) радиаторов, но так как вам необходима только одна секция, то выгодно приобрести один радиатор на одну секцию.
В третьей комнате существует \(7\) способов установить радиаторы: \([6, 0]\), \([5, 1]\), \([4, 2]\), \([3, 3]\), \([2, 4]\), \([1, 5]\), \([0, 6]\). Оптимальным будет являться вариант \([3, 3]\) и его стоимость равна \(3^2+ 3^2 = 18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 10000
10000 1
2 6
4 6
|
100000000
1
18
10
|