Problem Statement

You are given an array A of N integers, indexed from 1 to N . For any pair of indices i and j with 1 <= i < j <= N , the quirk of the pair is defined as Q(i, j) = (A[i] + A[i+1] + ... + A[j]) + c × (j² + j - i² + i) where c is a given integer constant. The first term is the sum of the contiguous block of A that starts at index i and ends at index j , with both endpoints included . Print the maximum value of Q(i, j) over all pairs of indices i , j with i < j . Input Format The first line contains the integer N (size of the array). The second line contains the constant c . The third line contains N space-separated integers denoting the array elements A[1], A[2], ..., A[N] . Output Format Print a single integer denoting the maximum quirk value. Constraints 2 <= N <= 2 × 10^5 -10^8 <= c <= 10^8 -10^9 <= A[i] <= 10^9 The answer always fits in a signed 64-bit integer, but it does not always fit in 32 bits. Example 1 Input 4 1 3 1 4 2 Output 30 Explanation Taking