Problem Description

Alice喜欢买玩具。

每一天刚开始时，商店里会上架一个新玩具。

如果玩具在它上架的第1天被Alice买走，它会给Alice带来$A_1$的快乐值。

如果玩具在它上架的第2天被Alice买走，它会给Alice带来$A_2$的快乐值。

如果玩具在它上架的第3天被Alice买走，它会给Alice带来$A_3$的快乐值。

如果3天都没被买走，在第4天刚开始时，该玩具会被下架。

一共有n天，第i天Alice可以购买不超过$b_i$个玩具。

她想知道她最多能得到多少快乐值。

Input

第一行一个正整数 $T$ 代表数据组数

对于每一组数据，输入两行。

第一行，包含四个正整数 $n,A_1,A_2,A_3$ ，表示天数，以及玩具被购买时产生的快乐值。

第二行共 $n$ 个数，第 $i$ 个数表示第 $i$ 天Alice可以购买的玩具数量 $b_i$。

$T\leq50000,1\leq n \leq 10^5，\sum_{n} \leq 10^6 , 0 \leq b_i \leq 3,0\leq a_i \leq 10^9$

Output

共 $T$ 行，每行一个整数表示最大快乐值。

2
5 3 2 1
1 0 1 0 3
5 1 2 3
1 0 1 0 3

11
9