Имеется n камней, пронумерованных 1, 2, ..., n. Для каждого i (1 ≤ i ≤ n) высота камня i равна h[i]
. Имеет место соотношение h[1]
< h[2]
< ... < h[n]
.
Лягушка изначально находится на камне 1. Он повторяет следующее действие несколько раз, чтобы добраться до камня n:
Если лягушка находится на камне i, она может прыгнуть на один из следующих: i + 1, i + 2, ..., n. Стоимость прыжка равна (h[j] − h[i])^2
+ c, где j - номер камня, на который она прыгнет.
Найдите минимальную стоимость, за которую лягушка сможет достигнуть камня n.
Первая строка содержит два целых числа n (2 ≤ n ≤ 2 * 10^5
) и c (1 ≤ c ≤ 10^12
). Вторая строка содержит высоты камней 1 ≤ h[1]
< h[2]
< ... < h[n]
≤ 10^6
.
Выведите наименьшую искомую стоимость.