Problem Statement

Alice, a merchant, has decided to earn gold over the next $N$ days. Initially, Alice has $10^{100}$ gold and does not have even $1$ jewel.

On day $i$, Alice can make the following two types of transactions.

• Pay $A_i$ gold to buy $1$ jewel. This transaction can be made at most $B_i$ times.
• Sell $1$ jewel to receive $C_i$ gold. This transaction can be made only when she has $1$ or more jewels, and can be made at most $D_i$ times.

In addition, Alice's house has a storage vault that can hold at most $K$ jewels. Any jewel that Alice does not put in the vault is lost by the next day, but a jewel put in the vault is not lost, and she can use the stored jewels for transactions on subsequent days.

What is the maximum amount of gold Alice can earn through the transactions over the $N$ days?

More precisely, let $S$ gold be the maximum possible amount of gold Alice has after finishing the transactions on day $N$. Find $S - 10^{100}$.

There are $T$ test cases in total.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $1 \le A_i,B_i,C_i,D_i \le 5 \times 10^6$
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• All input values are integers.

Input

The input is given from standard input in the following format. Here, $\text{case}_i$ is the $i$-th test case.

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_{T}$

$N\ K$
$A_1 \ A_2 \ldots A_N$
$B_1 \ B_2 \ldots B_N$
$C_1 \ C_2 \ldots C_N$
$D_1 \ D_2 \ldots D_N$

Output

Output $T$ lines. The $i$-th line should contain the answer for $\text{case}_i$.

Sample

3
3 2
1 3 2
3 3 1
2 1 3
1 3 2
4 1
4 2 1 3
5 6 2 3
7 3 1 9
5 1 4 8
13 4929798
1150434 88899 539811 1769519 4292449 4934296 4400709 64937 1760077 744701 456322 3779656 921043
1887669 2018657 3548740 193710 2991728 1964569 480243 2058687 4154332 3477027 3826799 1745255 2251591
3069743 1945307 3516424 4440181 1139192 489673 3089401 891641 1437747 2861899 984159 3969672 1605868
4638874 260809 499501 4269856 2551383 194827 2822117 1338907 2315113 866580 180577 1820692 1137521

5
42
37267031954271