Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Чай

URL первоисточника: http://ctddev.ifmo.ru/school/io/archive.html

Задачу добавил: alef

Успешно сдано решений: 9

Как хорошо выпить чай в купе во время поездки! Особенно хорошо это делать не в одиночку. В купе собралось N человек, и каждый пришел со своей кружкой. Кружка i-го человека вмещает Ai миллилитров воды. Вам, как проигравшему в интеллектуальную игру "О, Макс!", надо наполнить кипятком все кружки. Кипяток можно получить в конце вагона, но туда можно идти только с одной кружкой. Эта кружка может быть как пустой, так и частично наполненной. Она доливается кипятком (не обязательно полностью), и вы возвращаетесь назад в купе. Там вы можете произвольным образом переливать воду из кружки в кружку. Так как поезд оснащен новым цифровым паровым котлом, кипяток в кружку доливается всегда порциями в целое число миллилитров. За одну ходку за кипятком вы тратите энергию равную W^2+M, где W - это масса кипятка, долитого в кружку (вода, которая уже была в ней, не учитывается, так как успела уже остыть), а M - это масса вашего тела.
Какое наименьшее количество энергии необходимо потратить, чтобы наполнить водой все кружки в купе?

Формат входного файла
В первой строке входного файла записаны два целых числа N, M (1<=N<=50000, 0<=M<=10^9).
Далее во входном файле записана последовательность целых чисел A1,A2,...,AN (1<=Ai<=10^5).

Формат выходного файла
Выведите искомую величину в виде целого числа без лидирующих нулей.

Пример входного файла
2 5
2 2
Пример выходного файла
18

Пример входного файла
2 12
5 1

Пример выходного файла
42

 

Сдать задачу

Задать вопрос жюри по этой задаче