暂无测试数据。

对于数列 $a$，定义区间 $[l,r]$ 的分值为 $\sum\limits_{i=l}^r a_i^2-\sum\limits_{i=l}^r a_i-k\times (r-l+1)$。其中 $k$ 是一个给定的参数。

你获得了一个很短的数列，希望找到一个分值最大的区间，这个问题你可以轻松解决，你可以把所有的区间以及它们的分值都找了出来。

但是不服输的小蒜想要挑战你，因此他给了你一个很长的数列，你还能找到所有非空区间的分值的最大值吗？

提示：$\sum\limits_{i=l}^r a_i = a_{l} + a_{l + 1} + a_{l + 2} + \cdots + a_{r}$

---

形式化题意：

给定 $n,k$ 和序列 $\{a_n\}$，试求 $\max\limits_{1\leq l\leq r\leq n}\{\sum\limits_{i=l}^r a_i^2-\sum\limits_{i=l}^r a_i-k\times (r-l+1)\}$ 的结果。

输入格式

第一行两个正整数，分别表示 $n,k$。

接下来一行 $n$ 个正整数，表示数列 $a$。

变量含义如上述所示。

输出格式

输出一个整数，表示答案。

数据范围

• 对于 $50\%$ 的数据，$n\le 1000$。

• 对于另外 $50\%$ 的数据，没有特殊限制。

• 对于 $100\%$ 的数据，$1\le n\le 10^6,0 \leq a_i \leq 10^6, 0\le k\le 10^9$。

6 0
1 2 3 4 5 6

70

1 1234
10

-1144