#pragma GCC target("prefer-vector-width=512")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <atcoder/all>

// https://maspypy.github.io/library/flow/bflow.hpp
namespace maspy {
template <class Flow, class Cost>
struct MinCostFlow {
   private:
	static constexpr int SCALING_FACTOR = 2;
	using V_id = uint32_t;
	using E_id = uint32_t;

	struct Edge {
		friend struct MinCostFlow;

	   private:
		V_id frm, to;
		Flow flow, cap;
		Cost cost;
		E_id rev;

	   public:
		Edge() = default;

		Edge(const V_id frm_,
			 const V_id to_,
			 const Flow cap_,
			 const Cost cost_,
			 const E_id rev_)
			: frm(frm_), to(to_), flow(0), cap(cap_), cost(cost_), rev(rev_) {};

		[[nodiscard]] Flow residual_cap() const {
			return cap - flow;
		}
	};

   public:
	struct EdgePtr {
		friend struct MinCostFlow;

	   private:
		const MinCostFlow* instance;
		const V_id v;
		const E_id e;

		EdgePtr(const MinCostFlow* instance_, const V_id v_, const E_id e_)
			: instance(instance_), v(v_), e(e_) {};

		[[nodiscard]] const Edge& edge() const {
			return instance->g[v][e];
		}
		[[nodiscard]] const Edge& rev() const {
			const Edge& te = edge();
			return instance->g[te.to][te.rev];
		}

	   public:
		[[nodiscard]] V_id frm() const {
			return rev().to;
		}
		[[nodiscard]] V_id to() const {
			return edge().to;
		}
		[[nodiscard]] Flow flow() const {
			return edge().flow;
		}
		[[nodiscard]] Flow lower() const {
			return -rev().cap;
		}
		[[nodiscard]] Flow upper() const {
			return edge().cap;
		}
		[[nodiscard]] Cost cost() const {
			return edge().cost;
		}
		[[nodiscard]] Cost gain() const {
			return -edge().cost;
		}
	};

   private:
	V_id n;
	std::vector<std::vector<Edge>> g;
	std::vector<Flow> b;

   public:
	MinCostFlow(int n_) : n(n_) {
		g.resize(n);
		b.resize(n);
	}

	V_id add_vertex() {
		++n;
		g.resize(n);
		b.resize(n);
		return n - 1;
	}

	std::vector<V_id> add_vertices(const size_t size) {
		std::vector<V_id> ret;
		for (V_id i = 0; i < size; ++i) ret.emplace_back(n + i);
		n += size;
		g.resize(n);
		b.resize(n);
		return ret;
	}

	void add_edge(const V_id frm,
				  const V_id to,
				  const Flow lo,
				  const Flow hi,
				  const Cost cost) {
		const E_id e = g[frm].size(), re = frm == to ? e + 1 : g[to].size();
		assert(lo <= hi);
		g[frm].emplace_back(Edge{frm, to, hi, cost, re});
		g[to].emplace_back(Edge{to, frm, -lo, -cost, e});
		edges.emplace_back(EdgePtr{this, frm, e});
	}

	void add_source(const V_id v, const Flow amount) {
		b[v] += amount;
	}
	void add_sink(const V_id v, const Flow amount) {
		b[v] -= amount;
	}

   private:
	static Cost constexpr unreachable = std::numeric_limits<Cost>::max();
	Cost farthest;
	std::vector<Cost> potential, dist;
	std::vector<Edge*> parent;
	std::priority_queue<std::pair<Cost, int>,
						std::vector<std::pair<Cost, int>>,
						std::greater<std::pair<Cost, int>>>
		pq;
	std::vector<V_id> excess_vs, deficit_vs;
	std::vector<EdgePtr> edges;
	Edge& rev(const Edge& e) {
		return g[e.to][e.rev];
	}

	void push(Edge& e, const Flow amount) {
		e.flow += amount;
		g[e.to][e.rev].flow -= amount;
	}

	Cost residual_cost(const V_id frm, const V_id to, const Edge& e) {
		return e.cost + potential[frm] - potential[to];
	}

	bool dual(const Flow delta) {
		dist.assign(n, unreachable);
		parent.assign(n, nullptr);
		excess_vs.erase(remove_if(begin(excess_vs), end(excess_vs),
								  [&](const V_id v) {
									  return b[v] < delta;
								  }),
						end(excess_vs));
		deficit_vs.erase(remove_if(begin(deficit_vs), end(deficit_vs),
								   [&](const V_id v) {
									   return b[v] > -delta;
								   }),
						 end(deficit_vs));
		for (const auto v : excess_vs) pq.emplace(dist[v] = 0, v);
		farthest = 0;
		size_t deficit_count = 0;
		while (!pq.empty()) {
			const auto [d, u] = pq.top();
			pq.pop();
			if (dist[u] < d) continue;
			farthest = d;
			if (b[u] <= -delta) ++deficit_count;
			if (deficit_count >= deficit_vs.size()) break;
			for (auto& e : g[u]) {
				if (e.residual_cap() < delta) continue;
				const auto v = e.to;
				const auto new_dist = d + residual_cost(u, v, e);
				if (new_dist >= dist[v]) continue;
				pq.emplace(dist[v] = new_dist, v);
				parent[v] = &e;
			}
		}
		pq = decltype(pq)();
		for (V_id v = 0; v < n; ++v) {
			potential[v] += std::min(dist[v], farthest);
		}
		return deficit_count > 0;
	}

	void primal(const Flow delta) {
		for (const auto t : deficit_vs) {
			if (dist[t] > farthest) continue;
			Flow f = -b[t];
			V_id v;
			for (v = t; parent[v] != nullptr && f >= delta;
				 v = parent[v]->frm) {
				f = std::min(f, parent[v]->residual_cap());
			}
			f = std::min(f, b[v]);
			if (f < delta) continue;
			for (v = t; parent[v] != nullptr;) {
				auto& e = *parent[v];
				push(e, f);
				const size_t u = parent[v]->frm;
				parent[v] = nullptr;
				v = u;
			}
			b[t] += f;
			b[v] -= f;
		}
	}

	void saturate_negative(const Flow delta) {
		excess_vs.clear();
		deficit_vs.clear();
		for (auto& es : g)
			for (auto& e : es) {
				const Flow rcap = e.residual_cap();
				const Cost rcost = residual_cost(e.frm, e.to, e);
				if (rcost < 0 && rcap >= delta) {
					push(e, rcap);
					b[e.frm] -= rcap;
					b[e.to] += rcap;
				}
			}
		for (V_id v = 0; v < n; ++v)
			if (b[v] != 0) {
				(b[v] > 0 ? excess_vs : deficit_vs).emplace_back(v);
			}
	}

   public:
	template <typename T>
	std::pair<bool, T> solve() {
		potential.resize(n);
		for (auto& es : g)
			for (auto& e : es) {
				const Flow rcap = e.residual_cap();
				if (rcap < 0) {
					push(e, rcap);
					b[e.frm] -= rcap;
					b[e.to] += rcap;
				}
			}
		Flow inf_flow = 1;
		for (const auto& es : g)
			for (const auto& e : es)
				inf_flow = std::max(inf_flow, e.residual_cap());
		Flow delta = 1;
		while (delta <= inf_flow) delta *= SCALING_FACTOR;

		for (delta /= SCALING_FACTOR; delta; delta /= SCALING_FACTOR) {
			saturate_negative(delta);
			while (dual(delta)) primal(delta);
		}

		T value = 0;
		for (const auto& es : g)
			for (const auto& e : es) {
				value += T(e.flow) * e.cost;
			}
		value /= 2;

		if (excess_vs.empty() && deficit_vs.empty()) {
			return {true, value};
		} else {
			return {false, value};
		}
	}

	template <class T>
	T get_result_value() {
		T value = 0;
		for (const auto& es : g)
			for (const auto& e : es) {
				value += (T)(e.flow) * (T)(e.cost);
			}
		value /= (T)2;
		return value;
	}

	std::vector<Cost> get_potential() {
		std::fill(potential.begin(), potential.end(), 0);
		for (int i = 0; i < (int)n; i++)
			for (const auto& es : g)
				for (const auto& e : es)
					if (e.residual_cap() > 0)
						potential[e.to] = std::min(potential[e.to],
												   potential[e.frm] + e.cost);
		return potential;
	}

	std::vector<EdgePtr> get_edges() {
		return edges;
	}
};
}  // namespace maspy

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

// https://github.com/drken1215/algorithm/blob/master/GraphNetworkFlow/min_cost_b_flow_by_network_simplex_method.cpp
// Network Simplex Method
template <class FLOW, class COST> struct NetworkSimplex {
	struct Edge {
		int from, to;
		FLOW cap;
		COST cost;
		friend ostream& operator<<(ostream& s, const Edge& e) {
			return s << e.from << " -> " << e.to << " (" << e.cap << ", "
					 << e.cost << ")";
		}
	};
	struct Parent {
		int p, e;
		FLOW up, down;
	};

	// inner values
	int N, M;
	vector<Edge> edges;
	vector<FLOW> lowers;  // for edge i
	vector<FLOW> dss;	  // for node v (demand and supply)

	// intermediate results
	int BUCKET_SIZE, MINOR_LIMIT;
	vector<Parent> parents;
	vector<int> depth, nex, pre, candidates;

	// results
	bool feasible;
	COST total_cost;
	vector<FLOW> flows;
	vector<COST> pots;

	// constructor
	explicit NetworkSimplex(int n = 0) : N(n), dss(n) {
	}

	// debugger
	friend ostream& operator<<(ostream& s, const NetworkSimplex& ns) {
		s << "feasibility: " << (ns.feasible ? "true" : "false") << '\n';
		s << "optimal value: " << ns.total_cost << '\n';
		for (int i = 0; i < ns.M; i += 2) {
			auto e = ns.edges[i];
			s << e.from << " -> " << e.to << ": " << ns.flows[i / 2]
			  << " (remained cap: " << e.cap << ", cost: " << e.cost << ")\n";
		}
		for (int v = 0; v < ns.N; v++)
			cout << "node " << v << ": " << ns.pots[v] << '\n';
		return s;
	}

	// setter
	void add_edge(int from, int to, FLOW lower, FLOW upper, COST cost) {
		edges.push_back({from, to, upper - lower, cost});
		edges.push_back({to, from, 0, -cost});
		lowers.push_back(lower);
		dss[from] -= lower;
		dss[to] += lower;
		M = (int)edges.size();
	}
	void add_ds(int v, FLOW ds) {
		assert(v >= 0 && v < N);
		dss[v] += ds;
	}

	// solver
	pair<bool, COST> solve() {
		BUCKET_SIZE = max(int(sqrt(double(M)) * 0.2), 10);
		MINOR_LIMIT = max(int(BUCKET_SIZE * 0.1), 3);
		precompute();
		candidates.reserve(BUCKET_SIZE);
		int ei = 0;
		while (true) {
			for (int i = 0; i < MINOR_LIMIT; i++)
				if (!minor()) break;
			COST best = 0;
			int best_ei = -1;
			candidates.clear();
			for (int i = 0; i < (int)edges.size(); i++) {
				if (edges[ei].cap) {
					COST clen = edges[ei].cost + pots[edges[ei ^ 1].to] -
								pots[edges[ei].to];
					if (clen < 0) {
						if (clen < best) best = clen, best_ei = ei;
						candidates.push_back(ei);
						if ((int)candidates.size() == BUCKET_SIZE) break;
					}
				}
				ei++;
				if (ei == (int)edges.size()) ei = 0;
			}
			if (candidates.empty()) break;
			push_flow(best_ei);
		}
		if (!postcompute()) return {false, COST(-1)};
		else return {true, total_cost};
	}

	void connect(int a, int b) {
		nex[a] = b, pre[b] = a;
	}

	void precompute() {
		pots.assign(N + 1, 0);
		parents.resize(N), depth.assign(N + 1, 1);
		nex.assign((N + 1) * 2, 0), pre.assign((N + 1) * 2, 0);
		COST inf_cost = 1;
		for (int i = 0; i < M; i += 2) {
			inf_cost += (edges[i].cost >= 0 ? edges[i].cost : -edges[i].cost);
		}
		edges.reserve(M + N * 2);
		for (int i = 0; i < N; i++) {
			if (dss[i] >= 0) {
				edges.push_back({i, N, 0, inf_cost});
				edges.push_back({N, i, dss[i], -inf_cost});
				pots[i] = -inf_cost;
			} else {
				edges.push_back({i, N, -dss[i], -inf_cost});
				edges.push_back({N, i, 0, inf_cost});
				pots[i] = inf_cost;
			}
			int e = (int)edges.size() - 2;
			parents[i] = {N, e, edges[e].cap, edges[e ^ 1].cap};
		}
		depth[N] = 0;
		for (int i = 0; i < N + 1; i++) connect(i * 2, i * 2 + 1);
		for (int i = 0; i < N; i++)
			connect(i * 2 + 1, nex[N * 2]), connect(N * 2, i * 2);
	}

	bool postcompute() {
		for (int i = 0; i < N; i++) {
			edges[parents[i].e].cap = parents[i].up;
			edges[parents[i].e ^ 1].cap = parents[i].down;
		}
		feasible = true;
		for (int i = 0; i < N; i++) {
			if (dss[i] >= 0) {
				if (edges[M + i * 2 + 1].cap) feasible = false;
			} else {
				if (edges[M + i * 2].cap) feasible = false;
			}
		}
		if (!feasible) return false;
		total_cost = 0;
		flows.clear();
		for (int i = 0; i < M; i += 2) {
			flows.push_back(lowers[i / 2] + edges[i ^ 1].cap);
			total_cost += flows.back() * edges[i].cost;
		}
		pots.pop_back();
		return true;
	}

	void push_flow(int ei0) {
		int u0 = edges[ei0 ^ 1].to, v0 = edges[ei0].to, del_u = v0;
		FLOW flow = edges[ei0].cap;
		COST clen = edges[ei0].cost + pots[u0] - pots[v0];
		bool del_u_side = true;
		int lca = get_lca(u0, v0, flow, del_u_side, del_u);
		if (flow) {
			int u = u0, v = v0;
			while (u != lca)
				parents[u].up += flow, parents[u].down -= flow,
					u = parents[u].p;
			while (v != lca)
				parents[v].up -= flow, parents[v].down += flow,
					v = parents[v].p;
		}
		int u = u0, par = v0;
		auto p_caps =
			make_pair(edges[ei0].cap - flow, edges[ei0 ^ 1].cap + flow);
		COST p_diff = -clen;
		if (!del_u_side) {
			swap(u, par);
			swap(p_caps.first, p_caps.second);
			p_diff *= -1;
		}
		int par_e = ei0 ^ (del_u_side ? 0 : 1);
		while (par != del_u) {
			int d = depth[par], idx = u * 2;
			while (idx != u * 2 + 1) {
				if (idx % 2 == 0)
					d++, pots[idx / 2] += p_diff, depth[idx / 2] = d;
				else d--;
				idx = nex[idx];
			}
			connect(pre[u * 2], nex[u * 2 + 1]);
			connect(u * 2 + 1, nex[par * 2]);
			connect(par * 2, u * 2);
			swap(parents[u].e, par_e);
			par_e ^= 1;
			swap(parents[u].up, p_caps.first);
			swap(parents[u].down, p_caps.second);
			swap(p_caps.first, p_caps.second);
			int next_u = parents[u].p;
			parents[u].p = par;
			par = u;
			u = next_u;
		}
		edges[par_e].cap = p_caps.first;
		edges[par_e ^ 1].cap = p_caps.second;
	}

	bool minor() {
		if (candidates.empty()) return false;
		COST best = 0;
		int best_ei = -1;
		int i = 0;
		while (i < int(candidates.size())) {
			int ei = candidates[i];
			if (!edges[ei].cap) {
				swap(candidates[i], candidates.back());
				candidates.pop_back();
				continue;
			}
			COST clen =
				edges[ei].cost + pots[edges[ei ^ 1].to] - pots[edges[ei].to];
			if (clen >= 0) {
				swap(candidates[i], candidates.back());
				candidates.pop_back();
				continue;
			}
			if (clen < best) best = clen, best_ei = ei;
			i++;
		}
		if (best_ei == -1) return false;
		push_flow(best_ei);
		return true;
	}

	int get_lca(int u, int v, FLOW& flow, bool& del_u_side, int& del_u) {
		auto up_u = [&]() {
			if (parents[u].down < flow)
				flow = parents[u].down, del_u = u, del_u_side = true;
			u = parents[u].p;
		};
		auto up_v = [&]() {
			if (parents[v].up <= flow)
				flow = parents[v].up, del_u = v, del_u_side = false;
			v = parents[v].p;
		};
		if (depth[u] >= depth[v]) {
			int num = depth[u] - depth[v];
			for (int i = 0; i < num; i++) up_u();
		} else {
			int num = depth[v] - depth[u];
			for (int i = 0; i < num; i++) up_v();
		}
		while (u != v) up_u(), up_v();
		return u;
	}
};

void solve() {
	ll n, k;
	cin >> n >> k;
	vector<int> a(n), b(n), c(n), d(n);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) cin >> b[i];
	rep(i, 0, n) cin >> c[i];
	rep(i, 0, n) cin >> d[i];
	// maspy::MinCostFlow<ll, ll> mcf(n + 1);
	NetworkSimplex<ll, ll> mcf(n + 1);
	rep(i, 0, n) {
		mcf.add_edge(n, i, 0, b[i], a[i]);
	}
	rep(i, 0, n - 1) {
		mcf.add_edge(i, i + 1, 0, k, 0);
	}
	rep(i, 0, n) {
		mcf.add_edge(i, n, 0, d[i], -c[i]);
	}
	auto [f, ans] = mcf.solve();
	assert(f);
	cout << -ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	cin >> t;
	while (t--) solve();
}