Задача . G. Вася и максимальный заработок

Вася сильно устал от кредитов (из задачи 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\).

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