//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; 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); } long long ans = -1; // メモリ確保のオーバーヘッドを無くすための使い回し配列 vector temp_BestA(N + 1, -1); vector temp_BestB(M + 1, -1); vector active_k_A; vector active_k_B; for (int c = 1; c <= max_color; ++c) { if (I[c].empty() || J[c].empty()) continue; // --- A の限界半径を基準にするケース --- for (int i : I[c]) { int k = min(i - 1, N - i); long long val = S_A[i + k] - S_A[i - 1 - k]; if (temp_BestA[k] == -1) active_k_A.push_back(k); if (val > temp_BestA[k]) temp_BestA[k] = val; } for (int k : active_k_A) { long long mx_B = -1; // 条件を満たす j の範囲を二分探索で一発特定(if文を排除して高速化) auto it_start = lower_bound(J[c].begin(), J[c].end(), k + 1); auto it_end = upper_bound(J[c].begin(), J[c].end(), M - k); for (auto it = it_start; it < it_end; ++it) { int j = *it; long long val = S_B[j + k] - S_B[j - 1 - k]; mx_B = mx_B > val ? mx_B : val; } if (mx_B != -1) { ans = max(ans, temp_BestA[k] + mx_B); } } // --- B の限界半径を基準にするケース --- for (int j : J[c]) { int k = min(j - 1, M - j); long long val = S_B[j + k] - S_B[j - 1 - k]; if (temp_BestB[k] == -1) active_k_B.push_back(k); if (val > temp_BestB[k]) temp_BestB[k] = val; } for (int k : active_k_B) { long long mx_A = -1; auto it_start = lower_bound(I[c].begin(), I[c].end(), k + 1); auto it_end = upper_bound(I[c].begin(), I[c].end(), N - k); for (auto it = it_start; it < it_end; ++it) { int i = *it; long long val = S_A[i + k] - S_A[i - 1 - k]; mx_A = mx_A > val ? mx_A : val; } if (mx_A != -1) { ans = max(ans, temp_BestB[k] + mx_A); } } // 使い回すため初期化(O(N) ではなく O(使用したkの数) で済む) for (int k : active_k_A) temp_BestA[k] = -1; active_k_A.clear(); for (int k : active_k_B) temp_BestB[k] = -1; active_k_B.clear(); } cout << ans << "\n"; } int main() { // 高速入出力設定 ios_base::sync_with_stdio(false); cin.tie(NULL); int T; if (cin >> T) { while (T--) { solve(); } } return 0; }