题目内容

在一个时序数据分析任务中，给定长度为 $n$ 的正整数序列 $x_1, x_2, \dots, x_n$，表示每个时刻的信号强度。你需要对每个 $m = 1, 2, \dots, n$ 分别计算一个最小代价：你可以删除序列中任意位置的若干元素，删除总次数不能超过 $n-m$ 次；每删除一个元素需要支付 $k$ 的代价。设删除后剩下的序列为 $y_1, y_2, \dots, y_t$，则总代价定义为 $(删除次数) \times k + \sum_{i=1}^{m} y_i$（若剩余长度不足 $m$，此情况不会发生，因为最多删除 $n-m$ 次保证了剩余长度至少为 $m$）。每次对 $m$ 的计算都是独立的：你从完整的原始序列开始进行删除操作。求每个 $m$ 对应的最小可能总代价。

数据约束：序列长度 $n$ 满足 $1 \le n \le 1000$，删除单位代价 $k$ 满足 $1 \le k \le 2 \times 10^5$，每个信号强度 $x_i$ 均为整数且 $1 \le x_i \le 2 \times 10^5$。测试数据组数 $T$ 满足 $1 \le T \le 50$，且所有测试数据中 $n$ 的总和不超过 $1000$。

输入描述

第一行一个整数 $T$，表示测试数据组数。接下来每组数据包含两行：第一行两个整数 $n$ 和 $k$，第二行 $n$ 个整数 $x_1, x_2, \dots, x_n$。

输出描述