Sắp tới, chiến dịch airdrop token VNOI sẽ diễn ra trong thời lượng ~n~ giây. Mỗi người dùng, miễn là có tài khoản trên hệ thống VNOJ, đều có thể tham gia. Phần thưởng chia cho mỗi người dùng tham gia sẽ được quy đổi dựa trên số điểm mà người dùng đạt được trong chiến dịch. Khi đăng ký tham gia sự kiện ban đầu, người dùng sẽ nhận được ~s~ điểm mỗi giây từ hệ thống thưởng.

Người dùng có thể sử dụng điểm của mình để đầu tư vào ba danh mục: 1) nâng cấp hệ thống chấm điểm VNOJ, 2) nâng cấp chất lượng bài toán trên VNOJ, và 3) nâng cấp số lượng cuộc thi trên VNOJ. Danh mục đầu tư thứ ~i~ có tối đa ~l_i~ cấp độ đầu tư. Đối với mỗi danh mục, người dùng phải nâng cấp các cấp độ từ thấp nhất đến cao nhất. Để đạt được cấp độ ~j~ của danh mục đầu tư thứ ~i~, người dùng cần tiêu tốn ~c_{i,j}~ điểm. Đổi lại, sau khi nâng cấp, người dùng sẽ nhận thêm ~r_{i,j}~ điểm mỗi giây.

Cụ thể, người dùng bắt đầu ở giây ~0~ với ~0~ điểm. Đối với mỗi giây ~i~ từ ~0~ đến ~n~, hai sự kiện sau sẽ xảy ra theo thứ tự:

• Nếu ~i > 0~, người dùng nhận thêm điểm từ hệ thống thưởng.

• Người dùng có thể chọn nâng cấp bất kỳ số lượng cấp độ nào cho mỗi danh mục đầu tư, miễn là họ không vượt quá số điểm hiện có. Điều này sẽ làm giảm số điểm (có hiệu lực ngay lập tức), và tăng số điểm thưởng mỗi giây (có hiệu lực bắt đầu từ giây tiếp theo).

Là một nhà đầu tư khôn ngoan, bạn tham gia chiến dịch để tối đa hóa số điểm của mình. Tính toán số điểm tối đa mà bạn có thể nhận được sau khi chiến dịch kết thúc.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \leq t \leq 100~) – số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa hai số nguyên ~n, s~ (~1 \leq n, s \leq 10^9~) — thời gian của chiến dịch và số điểm ban đầu mà người dùng nhận được mỗi giây.

Tiếp theo là ba nhóm dòng tương ứng với ba danh mục đầu tư, với nhóm dòng thứ ~i~ cho ~3~ danh mục đầu tư như sau.

• Dòng đầu tiên chứa một số nguyên dương ~l_i~ (~1 \leq l_i \leq 200~) — số lượng cấp độ đầu tư cho danh mục thứ ~i~.

• Dòng thứ hai chứa ~l_i~ số nguyên ~c_{i,1}, c_{i, 2}, ..., c_{i, l_i}~ (~0 \leq c_{i,j} \leq 10^6~) — số điểm cần thiết để nâng cấp các cấp độ của danh mục đầu tư thứ ~i~.

• Dòng thứ ba chứa ~l_i~ số nguyên ~r_{i,1}, r_{i, 2}, ..., r_{i, l_i}~ (~0 \leq r_{i,j} \leq 10^6~) — số điểm nhận được mỗi giây sau khi nâng cấp các cấp độ của danh mục đầu tư thứ ~i~.

Đảm bảo rằng ~L_i \le 200~ với mọi ~1 \le i \le 3~, với ~L_i~ là tổng của ~l_i~ qua mọi test case.

Output

Với mỗi test case, in ra một số nguyên duy nhất – cho số điểm tối đa có thể nhận được sau khi chiến dịch kết thúc.

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

Chiến lược đầu tư tối ưu cho test case đầu tiên như sau:

1. Ở giây ~0~, bạn không làm gì. Cuối cùng, bạn có ~0~ điểm với tỷ lệ thưởng là ~5~ điểm mỗi giây.

2. Ở giây ~1~, bạn nhận thêm ~5~ điểm để đạt ~5~ điểm, và bạn không nâng cấp bất kỳ danh mục nào. Cuối cùng, bạn có ~5~ điểm với tỷ lệ thưởng là ~5~ điểm mỗi giây.

3. Ở giây ~2~, bạn nhận thêm ~5~ điểm để đạt ~10~ điểm. Bạn nâng cấp cấp độ đầu tiên của danh mục thứ ba, điều này tốn của bạn ~10~ điểm. Cuối cùng, bạn có ~0~ điểm với tỷ lệ thưởng là ~12~ điểm mỗi giây.

4. Ở giây ~3~, bạn nhận thêm ~12~ điểm để đạt ~12~ điểm. Bạn nâng cấp cấp độ đầu tiên và thứ hai của danh mục đầu tiên, điều này tốn của bạn ~11~ điểm. Cuối cùng, bạn có ~1~ điểm với tỷ lệ thưởng là ~20~ điểm mỗi giây.

5. Ở giây ~4~, bạn nhận thêm ~20~ điểm để đạt ~21~ điểm. Bạn nâng cấp cấp độ thứ hai của danh mục thứ ba, điều này tốn của bạn ~14~ điểm. Cuối cùng, bạn có ~7~ điểm với tỷ lệ thưởng là ~35~ điểm mỗi giây.

6. Ở giây ~5~, bạn nhận thêm ~35~ điểm để đạt ~42~ điểm. Bạn nâng cấp cấp độ đầu tiên của danh mục thứ hai và cấp độ thứ ba của danh mục thứ ba, điều này tốn của bạn ~36~ điểm. Cuối cùng, bạn có ~6~ điểm với tỷ lệ thưởng là ~54~ điểm mỗi giây.

Trong thời gian còn lại, bạn không nâng cấp thêm bất kỳ danh mục nào. Cuối cùng, bạn nhận được ~(10 - 5) \times 54 + 6 = 276~ điểm.