Задан массив \(a_1, a_2, \dots, a_n\), состоящий из \(n\) целых чисел. Также дано целое число \(x\).
Пусть \(f(k)\) будет равно максимальной сумме последовательного подмассива \(a\) после применения следующей операции: прибавить \(x\) к элементам на ровно \(k\) различных позициях. Пустой подмассив тоже рассматривается, его сумма равна \(0\).
Обратите внимание, что подмассив не обязан включать в себя все увеличенные элементы.
Посчитайте максимальное значение \(f(k)\) для каждого \(k\) от \(0\) до \(n\) независимо.
В первой строке записано одно целое число \(t\) (\(1 \le t \le 5000\)) — количество наборов входных данных.
В первой строке каждого набора записано два целых числа \(n\) и \(x\) (\(1 \le n \le 5000\); \(0 \le x \le 10^5\)) — количество элементов массива и значение для прибавления.
Во второй строке записаны \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(-10^5 \le a_i \le 10^5\)).
Сумма \(n\) по всем наборам целых чисел не превосходят \(5000\).
На каждый набор входных данных выведите \(n + 1\) целое число — максимальное значение \(f(k)\) для каждого \(k\) от \(0\) до \(n\) независимо.
В первом наборе не важно, к каким элементам прибавлять \(x\). Подотрезок с максимальной суммой всегда будет целым массивом. Если увеличить \(k\) элементов на \(x\), к сумме прибавится \(k \cdot x\).
Во втором наборе:
3 4 2 4 1 3 2 3 5 -2 -7 -1 10 2 -6 -1 -2 4 -6 -1 -4 4 -5 -4
10 12 14 16 18 0 4 4 5 4 6 6 7 7 7 7 8 8 8 8
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач