Vasya and Maximum Profit

Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.

Vasya has $$$n$$$ problems to choose from. They are numbered from $$$1$$$ to $$$n$$$. The difficulty of the $$$i$$$-th problem is $$$d_i$$$. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the $$$i$$$-th problem to the contest you need to pay $$$c_i$$$ burles to its author. For each problem in the contest Vasya gets $$$a$$$ burles.

In order to create a contest he needs to choose a consecutive subsegment of tasks.

So the total earnings for the contest are calculated as follows:

• if Vasya takes problem $$$i$$$ to the contest, he needs to pay $$$c_i$$$ to its author;
• for each problem in the contest Vasya gets $$$a$$$ burles;
• let $$$gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2$$$. If Vasya takes all the tasks with indices from $$$l$$$ to $$$r$$$ to the contest, he also needs to pay $$$gap(l, r)$$$. If $$$l = r$$$ then $$$gap(l, r) = 0$$$.

Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.