Критий прохід#3972
Ваш університет планує побудувати нову доріжку, і вони хочуть, щоб хоча б частина її була накрита. Є певні точки, які обов'язково мають бути накриті. Не важливо, чи будуть інші точки вздовж доріжки накриті чи ні.
Будівельний підрядник пропонує цікаву схему ціноутворення. Щоб накрити доріжку від точки до точки , вони стягуватимуть плату c+(x-y)^2, де — це константа. Зверніть увагу, що можливо, щоб x=y. У такому випадку підрядник стягне лише .
З огляду на точки вздовж доріжки та константу , яка мінімальна вартість накриття доріжки?
У вхідних даних буде кілька тестових випадків. Кожен тестовий випадок починається з рядка з двома цілими числами, (1 \le n \le 1000000) та (1 \le c \le 10^9), де — це кількість точок, які повинні бути накриті, а — константа підрядника. Кожен з наступних рядків містить одне ціле число, яке представляє точку вздовж доріжки, яку потрібно накрити. Точки подані в порядку зростання. Усі точки знаходяться в діапазоні від до 10^9, включно. Вхідні дані закінчуються рядком з двома .
Для кожного тестового випадку виведіть одне ціле число, яке представляє мінімальну вартість накриття всіх зазначених точок. Виведіть кожне число в окремому рядку, без пробілів, і не друкуйте порожніх рядків між відповідями. Усі можливі вхідні дані дають відповіді, які вміщуються в підписане -бітове ціле число.
Приклад 1