Вася сильно устал от кредитов (из задачи F) и теперь хочет заработать деньги сам! Для этого он решил подготовить контест.

Васе предложено $$$n$$$ задач. Они пронумерованы от $$$1$$$ до $$$n$$$. Сложность $$$i$$$-й задачи равна $$$d_i$$$. Кроме того, задачи заданы в возрастающем относительно сложности порядке. Сложности всех задач различны. Для того чтобы добавить $$$i$$$-ю задачу в контест Васе нужно заплатить $$$c_i$$$ бурлей автору. За каждую задачу в своем контесте Вася получит $$$a$$$ бурлей.

Для того чтобы создать контест нужно выбрать непрерывный подотрезок задач.

Суммарный заработок за контест считается следующим образом:

• если Вася берет задачу $$$i$$$ в контест, ему нужно заплатить $$$c_i$$$ её автору;
• за каждую добавленную задачу Вася получает $$$a$$$ бурлей;
• пусть $$$gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2$$$. Если Вася берет в контест все задачи с индексом от $$$l$$$ до $$$r$$$, он так же платит $$$gap(l, r)$$$. Если $$$l = r$$$ то $$$gap(l, r) = 0$$$.

Посчитайте максимальный Васин заработок, если он подготовит непрерывный подотрезок задач.