//generated by Gemini #include #include #include using namespace std; void solve() { int N, M; if (!(cin >> N >> M)) return; vector A(N + 1), B(M + 1); for (int i = 1; i <= N; ++i) cin >> A[i]; for (int j = 1; j <= M; ++j) cin >> B[j]; vector C(N + 1), D(M + 1); for (int i = 1; i <= N; ++i) cin >> C[i]; for (int j = 1; j <= M; ++j) cin >> D[j]; // 1. 累積和の計算 (1-indexed) vector S_A(N + 1, 0), S_B(M + 1, 0); for (int i = 1; i <= N; ++i) S_A[i] = S_A[i - 1] + A[i]; for (int j = 1; j <= M; ++j) S_B[j] = S_B[j - 1] + B[j]; // 2. 各インデックスの中心からの限界半径 lim を計算 vector limA(N + 1), limB(M + 1); for (int i = 1; i <= N; ++i) limA[i] = min(i - 1, N - i); for (int j = 1; j <= M; ++j) limB[j] = min(j - 1, M - j); // 3. 各色ごとにインデックスをグループ分け int max_color = N + M; vector> I(max_color + 1), J(max_color + 1); for (int i = 1; i <= N; ++i) { if (C[i] <= max_color) I[C[i]].push_back(i); } for (int j = 1; j <= M; ++j) { if (D[j] <= max_color) J[D[j]].push_back(j); } long long ans = -1; // 4. 各色について処理 for (int c = 1; c <= max_color; ++c) { if (I[c].empty() || J[c].empty()) continue; // 方法1と方法2の推定計算量を比較 long long cost1 = (long long)I[c].size() * J[c].size(); long long cost2_A = 0; for (int i : I[c]) cost2_A += limA[i]; long long cost2_B = 0; for (int j : J[c]) cost2_B += limB[j]; long long cost2 = cost2_A + cost2_B; if (cost1 <= cost2) { // 【方法1】 全ペア探索 for (int i : I[c]) { for (int j : J[c]) { int k = min(limA[i], limB[j]); long long valA = S_A[i + k] - S_A[i - 1 - k]; long long valB = S_B[j + k] - S_B[j - 1 - k]; ans = max(ans, valA + valB); } } } else { // 【方法2】 半径 k ごとの最大値配列を構築して合成 int max_lim_A = 0; for (int i : I[c]) max_lim_A = max(max_lim_A, limA[i]); int max_lim_B = 0; for (int j : J[c]) max_lim_B = max(max_lim_B, limB[j]); int max_k = min(max_lim_A, max_lim_B); vector f_A(max_k + 1, -1); for (int i : I[c]) { int L = min(limA[i], max_k); for (int k = 0; k <= L; ++k) { long long val = S_A[i + k] - S_A[i - 1 - k]; f_A[k] = max(f_A[k], val); } } vector f_B(max_k + 1, -1); for (int j : J[c]) { int L = min(limB[j], max_k); for (int k = 0; k <= L; ++k) { long long val = S_B[j + k] - S_B[j - 1 - k]; f_B[k] = max(f_B[k], val); } } for (int k = 0; k <= max_k; ++k) { if (f_A[k] != -1 && f_B[k] != -1) { ans = max(ans, f_A[k] + f_B[k]); } } } } cout << ans << "\n"; } int main() { // 高速入出力設定 ios_base::sync_with_stdio(false); cin.tie(NULL); int T; if (cin >> T) { while (T--) { solve(); } } return 0; }