该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【样例 1 输入】

3
3 5 2
2 5 3
6 0 2
1 1 4 5 1 4
7 10 3
1 9 1 9 8 1 0

【样例 1 输出】

6
64
2268

【数据范围】

对于 100% 的数据，1 ≤ 𝑇 ≤ 5,0 ≤𝑎𝑖 ≤ 𝑀 ≤ 5000,1 ≤ n ≤ 5000,0 ≤ k ≤ 10^9。