//generated by Gemini #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include #include #include using namespace std; void solve() { int N, M; if (!(cin >> N >> M)) return; // 累積和の構築(1-indexed) vector S_A(N + 1, 0), S_B(M + 1, 0); for (int i = 1; i <= N; ++i) { long long a; cin >> a; S_A[i] = S_A[i - 1] + a; } for (int j = 1; j <= M; ++j) { long long b; cin >> b; S_B[j] = S_B[j - 1] + b; } int max_color = N + M; vector> I(max_color + 1); vector> J(max_color + 1); for (int i = 1; i <= N; ++i) { int c; cin >> c; I[c].push_back(i); } for (int j = 1; j <= M; ++j) { int d; cin >> d; J[d].push_back(j); } // 各インデックスの限界半径(lim)と、その限界まで広げたときの理論上最大スコア(Max)を前計算 vector limA(N + 1), limB(M + 1); vector MaxA(N + 1), MaxB(M + 1); for (int i = 1; i <= N; ++i) { limA[i] = min(i - 1, N - i); MaxA[i] = S_A[i + limA[i]] - S_A[i - 1 - limA[i]]; } for (int j = 1; j <= M; ++j) { limB[j] = min(j - 1, M - j); MaxB[j] = S_B[j + limB[j]] - S_B[j - 1 - limB[j]]; } long long ans = -1; for (int c = 1; c <= max_color; ++c) { if (I[c].empty() || J[c].empty()) continue; // 【最重要最適化】: 探索前に ans の下界をヒューリスティックに一気に引き上げる // 1. Max(理論上最大スコア)が最大のペアを試す int best_max_i = I[c][0], best_max_j = J[c][0]; for(int i : I[c]) if(MaxA[i] > MaxA[best_max_i]) best_max_i = i; for(int j : J[c]) if(MaxB[j] > MaxB[best_max_j]) best_max_j = j; int k1 = min(limA[best_max_i], limB[best_max_j]); long long val1 = (S_A[best_max_i + k1] - S_A[best_max_i - k1 - 1]) + (S_B[best_max_j + k1] - S_B[best_max_j - k1 - 1]); if (val1 > ans) ans = val1; // 2. 限界半径 (lim) が最大のペアを試す int best_lim_i = I[c][0], best_lim_j = J[c][0]; for(int i : I[c]) if(limA[i] > limA[best_lim_i]) best_lim_i = i; for(int j : J[c]) if(limB[j] > limB[best_lim_j]) best_lim_j = j; int k2 = min(limA[best_lim_i], limB[best_lim_j]); long long val2 = (S_A[best_lim_i + k2] - S_A[best_lim_i - k2 - 1]) + (S_B[best_lim_j + k2] - S_B[best_lim_j - k2 - 1]); if (val2 > ans) ans = val2; // 理論上最大スコアの降順にソート sort(I[c].begin(), I[c].end(), [&](int a, int b) { return MaxA[a] > MaxA[b]; }); sort(J[c].begin(), J[c].end(), [&](int a, int b) { return MaxB[a] > MaxB[b]; }); // 枝刈り付き全探索 (Branch and Bound) for (int i : I[c]) { // A側の候補 i と、B側で最強の J[c][0] を組み合わせても ans 以下なら、完全終了 if (MaxA[i] + MaxB[J[c][0]] <= ans) break; for (int j : J[c]) { // 現在の i, j の理論上の最大値が ans 以下なら、これ以降の弱い j を見ても無駄なので break if (MaxA[i] + MaxB[j] <= ans) break; int k = min(limA[i], limB[j]); long long sum = (S_A[i + k] - S_A[i - k - 1]) + (S_B[j + k] - S_B[j - k - 1]); if (sum > ans) { ans = sum; } } } } cout << ans << "\n"; } int main() { // 高速入出力 ios_base::sync_with_stdio(false); cin.tie(NULL); int T; if (cin >> T) { while (T--) { solve(); } } return 0; }