题目描述

给定两个整数 $N$ 和 $K$，以及一个由 $N$ 个整数构成的数组 $A$。

你必须选择 $K$ 个互不相交且非空的子数组，使得得分最大化。

得分的计算规则如下：

$$\text{Score} = \sum_{i=1}^{K} (\text{Sum}[i] \times i)$$

其中，$\text{Sum}[i]$ 表示从左到右数第 $i$ 个被选中的子数组的元素之和。

注意：子数组不需要覆盖整个数组，允许数组中的某些元素不被任何子数组包含。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 个测试用例描述如下：

对于每个测试用例：

• 第一行包含两个整数 $N$ 和 $K$。
• 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

对于每个测试用例，输出一行一个整数，表示可以取得的最大得分。

样例

2
5 2
1 2 -1 3 1
5 2
-1 2 11 -23 12

11
37

样例说明

样例1解释：

选 $[1,2]$ 和 $[3,1]$：$(1+2)\times1 + (3+1)\times2 = 3+8=11$。

样例2解释： 最优方案是选择子数组 $[2, 11]$ 作为第 $1$ 个子数组，选择子数组 $[12]$ 作为第 $2$ 个子数组。 得分为 $(2+11) \times 1 + 12 \times 2 = 13 + 24 = 37$。

数据范围

• $1 \le T \le 1000$
• $1 \le N \le 10^5$
• $1 \le K \le \min(100, N)$
• $-10^6 \le A_i \le 10^6$
• 所有测试用例中 $N$ 的总和不超过 $10^5$