Soon enough, the VNOI token airdrop campaign will take place over a duration of ~n~ seconds. Any user with an account on the VNOJ system can participate. The rewards distributed to each participating user will be based on the number of points the user earns during the campaign. Upon registering for the event initially, the user will receive ~s~ points per second from the bonus system.

Users can use their points to invest in three categories: 1) upgrade the VNOJ judging system, 2) upgrade the quality of problems on VNOJ, and 3) upgrade the number of contests on VNOJ. The ~i~-th investment category has a maximum of ~l_i~ investment levels. For each category, users must upgrade the levels from the lowest to the highest. To reach level ~j~ of the ~i~-th investment category, users need to spend ~c_{i,j}~ points. In return, after upgrading, users will receive an additional ~r_{i,j}~ points per second.

Formally, users start at second ~0~ with ~0~ points. For each second ~i~ from ~0~ to ~n~, the following happens in order:

• If ~i > 0~, users receive additional points from the bonus system.

• Users can now choose to upgrade any number of levels for each investment category, provided that they do not exceed their current points. This decreases their points (which happens immediately) and increases their bonus reward per second (which comes into effect at the start of the next second).

As a wise investor, you participate in the campaign to maximize your points. Calculate the maximum number of points you can receive after the campaign ends.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 100~). The description of each test case is as follows.

The first line contains two integers ~n, s~ (~1 \leq n, s \leq 10^9~) — the duration of the campaign and the initial points the user receives each second.

Following this are three groups of lines corresponding to the three investment categories, with the ~i~-th group of lines for the ~3~ investment categories as follows.

• The first line contains a positive integer ~l_i~ (~1 \leq l_i \leq 200~) — the number of investment levels for the ~i~-th category.

• The second line contains ~l_i~ integers ~c_{i,1}, c_{i, 2}, ..., c_{i, l_i}~ (~0 \leq c_{i,j} \leq 10^6~) — the points required to upgrade the levels of the ~i~-th investment category.

• The third line contains ~l_i~ integers ~r_{i,1}, r_{i, 2}, ..., r_{i, l_i}~ (~0 \leq r_{i,j} \leq 10^6~) — the points received per second after upgrading the levels of the ~i~-th investment category.

It is guaranteed that ~L_i \le 200~ for all ~1 \le i \le 3~, with ~L_i~ being the sum of ~l_i~ over all test cases.

Output

For each test case, output a single integer — the maximum points that can be received after the campaign.

Scoring

Sample Input 1

2
10 5
2
7 4
2 6
1
13
8
3
10 14 23
7 15 11
4 1
7
1 1 1 1 0 1 0
1 1 1 1 0 0 1
1
0
1
7
1 0 1 1 1 0 1
0 1 1 0 1 1 0

Sample Output 1

276
16

Notes

The optimal investment strategy for the first test case is as follows:

1. In second ~0~, you do nothing. By the end, you have ~0~ points with a bonus rate of ~5~ points per second.

2. In second ~1~, you get an additional ~5~ points to get to ~5~ points, and you do not upgrade any category. By the end, you have ~5~ points with a bonus rate of ~5~ points per second.

3. In second ~2~, you get an additional ~5~ points to get to ~10~ points. You upgrade the first level of the third category, which costs you ~10~ points. By the end, you have ~0~ points with a bonus rate of ~12~ points per second.

4. In second ~3~, you get an additional ~12~ points to get to ~12~ points. You upgrade the first and second levels of the first category, which costs you ~11~ points. By the end, you have ~1~ point with a bonus rate of ~20~ points per second.

5. In second ~4~, you get an additional ~20~ points to get to ~21~ points. You upgrade the second level of the third category, which costs you ~14~ points. By the end, you have ~7~ points with a bonus rate of ~35~ points per second.

6. In second ~5~, you get an additional ~35~ points to get to ~42~ points. You upgrade the first level of the second category and the third level of the third category, which costs you ~36~ points. By the end, you have ~6~ points with a bonus rate of ~54~ points per second.

In the remaining time, you do not upgrade any further categories. In the end, you receive ~(10 - 5) \times 54 + 6 = 276~ points.