신발 공장

어떤 회사가 신발 공장을 운영하고 있습니다. 신발 한 켤레를 만드는 데 드는 생산 비용은 $K$입니다.

시장 조사를 통해 길이가 $N$인 자연수 수열 $A$를 얻었습니다. $A_i$ ($1 \le i \le N$)는 지불할 수 있는 최대 가격이 정확히 $i$인 사람의 수, 즉 한 켤레의 가격이 $i$ 이하일 때에만 신발을 사는 사람의 수를 뜻합니다.

가격을 $p$로 정하면 지불 가능한 최대 가격이 $p$ 이상인 사람이 모두 한 켤레씩 사므로, 구매자 수는 $A_p + A_{p+1} + \dots + A_N$입니다. 각 구매자는 $p$를 내고 한 켤레의 생산 비용은 $K$이므로, 이때의 이익(판매액에서 생산 비용을 뺀 값)은

$(A_p + A_{p+1} + \dots + A_N) \cdot (p - K)$

입니다. $1 \le p \le N$을 만족하는 모든 가격 $p$ 중에서 이익이 가장 큰 값을 구하세요. 생산 비용이 가능한 모든 가격보다 크면 이 최댓값은 음수가 될 수도 있습니다.

첫째 줄에 테스트 집합의 수 $Z$ ($1 \le Z \le 10$)가 주어집니다.

각 테스트 집합은 두 줄로 이루어집니다. 첫째 줄에는 두 정수 $N$과 $K$ ($1 \le N, K \le 10^5$)가 주어집니다. 둘째 줄에는 $N$개의 정수 $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^5$)이 공백으로 구분되어 주어집니다.

각 테스트 집합마다 공장이 얻을 수 있는 최대 이익을 한 줄에 하나씩 출력하세요.

가격을 $p$로 정하면 지불 가능한 최대 가격이 $p$ 이상인 사람이 모두 사므로 구매자 수는 $A_p + \dots + A_N$이고, 한 켤레마다 $p - K$의 이익이 남습니다. 예를 들어 $A = [5, 4, 3, 2, 1]$이고 $K = 1$일 때 가격을 $3$으로 정하면 구매자는 $3 + 2 + 1 = 6$명이고 이익은 $6 \cdot (3 - 1) = 12$이며, 이것이 최댓값입니다. 가능한 모든 가격에 대해 이 값을 계산한 뒤 그중 최댓값을 출력하면 됩니다.