请问您要来点兔子吗？

题号：NC214521
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

智乃酱的店中有一排 n 只兔子，智乃酱想要从中选出一些兔兔参加比赛。每一只兔子都有一个能力值，这个能力值有正有负，由于智乃酱不想让选出的兔子分布过于集中或者分散，她规定每连续的 k 只兔子中至少要选 L 只，至多选 R 只。例如当 n=5, k=2, L=1, R=2时，表示如下的限制条件

1、第 1 只和第 2 只兔子中至少选 1 只参加比赛，至多选 2 只参加比赛。

2、第2只和第 3 只兔子中至少选 1 只参加比赛，至多选 2 只参加比赛。

3、第 3 只和第 4 只兔子中至少选 1 只参加比赛，至多选 2 只参加比赛。

4、第 4 只和第 5 只兔子中至少选 1 只参加比赛，至多选 2 只参加比赛。

请问智乃酱能够选出兔子的能力值之和最大为多少？

第一行输入一个正整数 T，表示有 T 组测试案例。

对于每组测试样例：

首先输入一个正整数 

接下来一行 n 个整数 

接下来一行输入三个正整数

所有测试数据的 n 之和小于 300000
##

仅一行一个整数，表示所选兔子能力值的最大和。

示例1

复制

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

复制