#include <bits/stdc++.h>
 using namespace std;

 struct MinCostFlow {
     struct Edge {
         int to, rev;
         long long cap, cost;
     };
     int N;
     vector<vector<Edge>> g;
     vector<long long> pot, dist;
     vector<int> pv_v, pv_e;

     MinCostFlow(int n): N(n), g(n), pot(n), dist(n), pv_v(n), pv_e(n) {}

     void add_edge(int fr, int to, long long cap, long long cost) {
         Edge a{to, (int)g[to].size(), cap, cost};
         Edge b{fr, (int)g[fr].size(), 0, -cost};
         g[fr].push_back(a);
         g[to].push_back(b);
     }

     // Capacity scaling min-cost flow: augment only edges with cap>=delta
     long long min_cost_profit_flow(int s, int t) {
         const long long INF = (1LL<<62);
         long long total_cost = 0;

         long long maxcap = 0;
         for (int v=0; v<N; v++) {
             for (auto &e: g[v]) maxcap = max(maxcap, e.cap);
         }
         long long delta = 1;
         while (delta <= maxcap) delta <<= 1;
         delta >>= 1;

         while (delta > 0) {
             while (true) {
                 // Dijkstra with reduced costs, only edges with cap>=delta
                 fill(dist.begin(), dist.end(), INF);
                 dist[s] = 0;
                 priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
                 pq.push({0, s});

                 while (!pq.empty()) {
                     auto [d, v] = pq.top(); pq.pop();
                     if (d != dist[v]) continue;
                     for (int i=0;i<(int)g[v].size();i++) {
                         Edge &e = g[v][i];
                         if (e.cap < delta) continue;
                         long long nd = d + e.cost + pot[v] - pot[e.to];
                         if (nd < dist[e.to]) {
                             dist[e.to] = nd;
                             pv_v[e.to] = v;
                             pv_e[e.to] = i;
                             pq.push({nd, e.to});
                         }
                     }
                 }

                 if (dist[t] == INF) break;
                 long long shortest = dist[t] + pot[t] - pot[s];
                 if (shortest >= 0) break;

                 for (int v=0; v<N; v++) if (dist[v] < INF) pot[v] += dist[v];

                 long long addf = LLONG_MAX;
                 for (int v=t; v!=s; v=pv_v[v]) {
                     Edge &e = g[pv_v[v]][pv_e[v]];
                     addf = min(addf, e.cap);
                 }
                 // we can safely push full addf (>=delta guaranteed)
                 for (int v=t; v!=s; v=pv_v[v]) {
                     Edge &e = g[pv_v[v]][pv_e[v]];
                     e.cap -= addf;
                     g[v][e.rev].cap += addf;
                 }
                 total_cost += addf * shortest;
             }
             delta >>= 1;
         }
         return total_cost;
     }
 };

 int main() {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);

     int T;
     cin >> T;
     while (T--) {
         int N;
         long long K;
         cin >> N >> K;
         vector<long long> A(N+1), B(N+1), C(N+1), D(N+1);
         for (int i=1;i<=N;i++) cin >> A[i];
         for (int i=1;i<=N;i++) cin >> B[i];
         for (int i=1;i<=N;i++) cin >> C[i];
         for (int i=1;i<=N;i++) cin >> D[i];

         int S = 0;
         int Tnode = N + 1;
         MinCostFlow mcf(N + 2);

         for (int i=1;i<=N;i++) {
             mcf.add_edge(S, i, B[i], A[i]);      // buy
             mcf.add_edge(i, Tnode, D[i], -C[i]); // sell
             if (i < N) mcf.add_edge(i, i+1, K, 0); // store
         }

         long long cost = mcf.min_cost_profit_flow(S, Tnode);
         long long profit = -cost;
         cout << profit << "\n";
     }
     return 0;
 }