태양광 충전

문제

Albert는 최근 태양광으로 충전되는 배터리를 구입했는데, 이를 활용하여 전기를 아껴보려고 한다. 이 배터리는 충전하면서 동시에 사용할 수 없는 단점이 있다. 그래서 하루에 한 번 아침에 태양광 배터리를 충전 할지 혹은 사용할지 정하려고 한다 -- 이보다 더 자주 바꾸는 것은 너무 번거롭기 때문이다.

우선, 현재 배터리는 $B$ 만큼 충전된 상태이며 최대 충전량은 $C$ 이다. $i$ 번째 날에는 정확히 $D\_i$ 만큼의 전기를 사용할 예정이다. 만약 $i$ 번째날 배터리의 충전량이 $D\_i$ 이상이라면 배터리로 가전 제품을 사용할 수 있고, 배터리의 충전량은 $D\_i$ 만큼 감소한다. 이 날은 일반 가정용 전기를 사용하지 않으므로 비용을 지불하지 않는다. 만약 $i$ 번째 날 배터리를 충전한다면 배터리의 충전량은 $P\_i$ 만큼 증가하지만 최대 충전량인 $C$ 를 넘을 수 없다. 배터리를 충전하면서 동시에 사용할 수 없으므로, 이 날은 일반 가정용 전기를 사용하고 비용을 지불해야한다. Albert가 사는 곳의 전기 사용료는 매일 바뀌는데, $i$ 번째 날에는 단위 사용량 당 $F\_i$ 만큼을 지불해야 하므로 총 $D\_i \cdot F\_i$ 를 지불해야한다.

위와 같은 조건 하에서 Albert는 앞으로 $N$ 일간 최소의 비용을 지불하고 동시에 $N$ 일째를 마쳤을 때 배터리 충전량이 처음 충전량보다 적지 않도록 하고 싶다 (즉 $N$ 일째를 마친 후 배터리는 $B$ 이상 충전 되어있어야 한다).

예를 들어 $N = 4$ , $B = 0$ , $C = 10$ , $P = \[10, 10, 10, 1]$ , $F = \[100, 100, 100, 100]$ , $D = \[4, 3, 2, 1]$ 이라 하자.

처음 배터리는 0만큼 충전된 상태이고 최대 10까지 충전 가능하다.
1일째: $D\_i$ = 4 이므로 4만큼의 전기가 필요하고 이 비용은 $F\[1] \cdot D\[1]$ = 400 이다. 그 동안 배터리를 충전하여 충전량이 $P\[1]$ = 10이 된다.
2-4일째: 3일간 총 사용량이 3 + 2 + 1 = 6 이므로 충전된 배터리를 사용하면 전기 사용료를 안 내도 된다. 마지막 날이 지난 후 배터리의 잔여량은 4 이다.
이 방법은 최종 배터리 잔여량이 $B$ 이상 되도록 하며 최소한의 비용을 지불하는 방법이다.

다른 예로 $N = 4$ , $B = 10$ , $C = 10$ , $P = \[10, 10, 10, 1]$ , $F = \[100, 100, 100, 100]$ , $D = \[4, 3, 2, 1]$ 이라 하자.

다른 값은 앞선 예제와 동일하지만 처음 배터리가 이미 완전히 충전 되어있다 ( $B = 10$ ).
1-2일째: 이틀간 이미 충전된 배터리를 사용하면 비용을 지불하지 않아도 된다. 2일째를 마친 후 배터리의 충전량은 3이 되어있다.
3일째: 배터리를 충전하면 3 + 10 = 13 이지만 최대 충전량인 10을 넘을 수 없으므로 10만큼 충전된 상태가 된다. 전기 사용료는 200을 지불해야한다.
4일째: 배터리를 충전하더라도 이미 최대로 충전된 상태이므로 변화가 없다. 전기 사용료는 100을 지불한다.
이 방법은 최종 배터리 잔여량이 $B$ 이상 되도록 하며 최소한의 비용을 지불하는 방법이다 (총 300을 지불한다).

위와 같이 $N, B, C, P, F, D$ 정보가 주어졌을 때, Albert가 매일 필요한 만큼 전기를 사용하면서 $N$ 일째를 마쳤을 때 배터리 충전량이 처음 충전량보다 적지 않도록 할 때 최소로 지불해야하는 비용을 계산해보자.

입력

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$ , $B$ , $C$ 값이 순서대로 공백으로 구분되어 주어진다. 둘째 줄에는 매일 태양광을 통해 배터리를 얼마나 충전할 수 있는지 나타내는 배열 $P$ 가 공백으로 구분되어 주어진다. 셋째 줄에는 매일 변하는 전기 단위 사용료를 나타내는 배열 $F$ 가 공백으로 구분되어 주어진다. 넷째 줄에는 매일 사용할 전기량을 나타내는 배열 $D$ 가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답인 최소 전기 사용료를 각 줄에 출력한다.

제한

$1 \le T \le 10$
$1 \le N, C \le 1000$
$0 \le B \le C$
$1 \le i \le N$ 인 각 $i$ 에 대하여:
- $1 \le D\_i, P\_i \le 1000$
- $1 \le F\_i \le 10^9$