Migrated from Lutece 3009 跳蘑菇

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在盛典与慧业当中，许多学派的代表都参加并完成了各种活动，并获得了丰厚的奖励，有的拿到了摩拉，有的拿到了限量七圣召唤卡牌，但可怜的旅行者辛辛苦苦忙活半天，都不够十连抽，于是善(e)良(xin)的策划准备给旅行者一个额外的可能获得奖励也可能失去原有原石的机会。

这个机会是一个跳蘑菇的游戏，这种跳跳菇在须弥很常见，它会有三种状态，分别是受到火，草，雷元素影响下的状态。为了防止旅行者摔伤，策划对游戏中的蘑菇进行了改造，其中失活状态（火元素）可以由左边 $k_1$ 个蘑菇跳过来（比如 $i$ 号蘑菇，）；原状态（草元素）可以由左边 $k_2$ 个蘑菇跳过来；激活状态（雷元素）可以由左边 $k_3$ 个蘑菇跳过来（$1\leq k_1<k_2<k_3$）。现在有一排 $n+2$ 个蘑菇均匀间隔排列在一起，旅行者要从左边第$0$号蘑菇起跳，每次只能往右边跳，跳到第 $n+1$ 个位置则停下来，保证第 $0,n+1$ 号位置的蘑菇是激活状态且没有宝箱，其他每个蘑菇上都有一个宝箱，其值为$w_i$，如果 $w_i>0$ 每次到达该蘑菇打开宝箱会获得 $w_i$ 原石，当然，$w_i<0$ 时也有可能是宝箱怪，会被吸走$-w_i$原石。

旅行者很苦恼，由于蘑菇很多，她和派蒙想了很久都不能想出获取最多原石或者损失最小的跳法，现在游戏活动快结束了，你能以最快告诉旅行者她最优策略的结果吗？

Input

第一行一个整数 $T$，表示有 $T$ 次这个活动。

对于每一次活动，输入格式如下：

第一行四个整数 $n,k_1,k_2,k_3$ 表示有宝箱蘑菇个数和对应三种蘑菇可以跳过来的距离。

接下来一行 $n$ 个数字 $w_i$ 表示第 $i$ 个蘑菇上面宝箱的价值。

接下来一行 $n$ 个数字 $t_i$ 表示第 $i$ 个蘑菇的类型（失活状态，原状态，激活状态分别用整数 $1,2,3$ 表示）

Output

对于每次活动，输出一个数字，表示旅行者能获得的最大原石数量（若会失去原石，则输出一个负数，其绝对值表示最少失去原石数量）

Samples

3
6 1 2 3
1 1 -4 5 1 -4
1 2 3 1 2 3
8 2 3 4
1 -9 1 -9 8 1 -10 11
1 1 1 2 2 2 3 3
4 1 2 3
-1 -2 -3 -4
1 1 1 1

4
22
-3

Constraints

$1\leq n\leq 10^5, 1\leq k_1 < k_2 < k_3 \leq n$

$|w_i|\leq 10000, t_i\in\{1,2,3\}$

$1\leq\sum n\leq 10^6$

Note

样例第一次活动是$0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 7$，所以答案是$1+1-4+5+1=4$。

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming