No testdata at current.

P2033.第2题-数组求和

1000ms

Difficulty: 10

所属公司 : 拼多多

题目内容

塔塔君有一长度为 $n$ 的输出数组，他需要对这个数组进行 $k$ 次插入操作，每次操作可以在当前数组任意位置插入一个数字，这个数字是当前数组的某个连续子数组（可以为空）中元素之和。塔塔君希望经过 $k$ 次操作之后，最终数组总和最大。

第一行包含一个整数 $T$ ( $1≤T≤10000$ )，表示总共有 $T$ 组样例

接下来每组样例包含两行：

第一行包含两个整数 $n$ 和 $k$ ( $1≤n,k≤10000$ )

$n$ 表示初始数字长度, $k$ 表示总计需要进行 $k$ 次插入操作

第二行包含 $n$ 整数 $a_1,a_2,...,a_n$ ( $-10^9≤a_i≤10^9,1≤i≤n$ )

包含 $T$ 行

每一行包含一个整数，即经过 $k$ 次插入操作后，可能的最大数组总和，因为数组总和肯能很大，输出总和对 $10^9+7$ 取模作为答案

输入

3
3 3
2 2 8
2 2
-4 -7
7 2
8 14 -9 6 0 -1 3

输出

96
999999996
87

输入

预期输出（选填）