Ta thấy, nếu mục tiêu sau khi kết thúc chiến dịch là nâng cấp được ~i, j, k~ mức ở lần lượt ba danh mục đầu tư, ta sẽ cố gắng để đạt được ba mức này sớm nhất với số điểm còn dư là nhiều nhất. Chứng minh:

Xét hai trạng thái để đạt được ba mức ~i, j, k~ là ~t_1, p_1~ và ~t_2, p_2~ với ~t_1, t_2~ là thời điểm đạt được ba mức đầu tư này và ~p_1, p_2~ là số điểm còn dư (~t_1 < t_2, p_1 < p_2~).

Trong chiến lược đầu tư tối ưu, nếu mục tiêu tiếp theo là nâng cấp một mức ~x~ bất kì, ta sẽ nâng cấp ngay khi có đủ số điểm tích lũy.

Gọi ~s~ là tổng số điểm cần bỏ ra để nâng cấp đến ba mức ~i, j, k~ ở ba danh mục đầu tư:

• Với trường hợp ~1~, tổng số điểm người chơi đã từng tạo ra tại thời điểm ~t_1~ sẽ không nhỏ hơn ~s~ (1)
• Với trường hợp ~2~, tổng số điểm người chơi đã từng tạo ra tại thời điểm ~t_2 - 1~ sẽ nhỏ hơn ~s~ (2)

Mà ~t_1 \le t_2 - 1~, từ (1) và (2) ta suy ra tại thời điểm ~t_2-1~, số điểm người chơi đã từng tạo ra trong trường hợp ~1~ sẽ lớn hơn hoặc bằng trường hợp ~2~.

Sau ~1~ giây từ thời điềm ~t_2-1~ đến ~t_2~, trường hợp ~1~ sẽ nhận được nhiều điểm thưởng hơn do tập các mức đã nâng cấp chứa tập các mức mà trường hợp hai đã nâng cấp.

Đến thời điểm ~t_2~, cả hai trường hợp sẽ có cùng tập các mức đã được nâng cấp, nhưng trường hợp ~1~ còn dư nhiều điểm hơn so với trường hợp ~2~.

Gọi ~dp_{i, j, k}~ là trạng thái trả về thời gian nhỏ nhất và số điểm còn dư nhiều nhất để đạt được ba mức ~i, j, k~.

Trạng thái xuất phát ~dp_{0, 0, 0} = {0, 0}~.

Để chuyển trạng thái, xét các mức tiếp theo của ba mục, tính thời gian nhỏ nhất và số điểm còn dư để đạt được mục này.

Để tính đáp án, xét tất cả các mức ~i, j, k~ mà sẽ được nâng cấp trong chiến dịch, gọi ~t~ là thời gian cần thiết, ~p~ là số điểm còn dư. Điểm số mà người chơi nhận được khi chiến dịch kết thúc được tính theo công thức: ~p + r \times (n - t)~ với ~r~ là số điểm thưởng mỗi giây.

#include <bits/stdc++.h>

using namespace std;
const int MAXL = 301;
const int INF = 2e9 + 7;

int n, s;
int l[4];
int r[4][MAXL];
int c[4][MAXL];
int sum[4][MAXL];
pair<int, long long> dp[MAXL][MAXL][MAXL];

pair<int, long long> calc(int cost, int time, long long point, int reward) {
    if (point >= cost) {
        return make_pair(time, -(point - cost));
    }
    int need = cost - point;
    int sec = (reward + need - 1) / reward;
    return make_pair(time + sec, -(point + 1LL * reward * sec - cost));
}

int getReward(int i, int j, int k) {
    return sum[1][i] + sum[2][j] + sum[3][k] + s;
}

void minimize(pair<int, long long> &a, pair<int, long long> b) {
    a = min(a, b);
}

int main() {
    int t; cin >> t;
    while (t--) {
        cin >> n >> s;
        for (int i = 1; i <= 3; ++i) {
            cin >> l[i];
            for (int j = 1; j <= l[i]; ++j) {
                cin >> c[i][j];
            }
            for (int j = 1; j <= l[i]; ++j) {
                cin >> r[i][j];
                sum[i][j] = sum[i][j - 1] + r[i][j];
            }
        }


        for (int i = 0; i <= l[1]; ++i) {
            for (int j = 0; j <= l[2]; ++j) {
                for (int k = 0; k <= l[3]; ++k) {
                    dp[i][j][k] = make_pair(INF, -INF);
                }
            }
        }

        dp[0][0][0] = make_pair(0, 0);
        long long ans = 0;

        for (int i = 0; i <= l[1]; ++i) {
            for (int j = 0; j <= l[2]; ++j) {
                for (int k = 0; k <= l[3]; ++k) {
                    if (dp[i][j][k].first > n) {
                        continue;
                    }
                    int reward = getReward(i, j, k);
                    if (i < l[1]) {
                        minimize(dp[i + 1][j][k], calc(c[1][i + 1], dp[i][j][k].first, -dp[i][j][k].second, reward));
                    }
                    if (j < l[2]) {
                        minimize(dp[i][j + 1][k], calc(c[2][j + 1], dp[i][j][k].first, -dp[i][j][k].second, reward));
                    }
                    if (k < l[3]) {
                        minimize(dp[i][j][k + 1], calc(c[3][k + 1], dp[i][j][k].first, -dp[i][j][k].second, reward));
                    }

                    ans = max(ans, -dp[i][j][k].second + 1LL * reward * (n - dp[i][j][k].first));
                }
            }
        }

        cout << ans << "\n";
    }
}