#define _CRT_SECURE_NO_WARNINGS
#define MAX(A, B) A > B ? A : B
#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int N, M;
int A[3001];
int B[101];
int cache[6][4][4][2];
int snack(int a, int b1, int b2, bool skip) {
int& rt = cache[a][b1][b2][skip];
if (rt != -1) return rt;
cout << a << ' ' << b1 << ' ' << b2 << ' ' << skip << '\n';
rt = 0;
if (skip) {
if (a < N) rt = snack(a + 1, b1, b2, 0);
if (b1 <= b2) {
rt = MAX(rt, snack(a, b1 + 1, b2, 0));
rt = MAX(rt, snack(a, b1, b2 - 1, 0));
}
}
else {
if (a < N) rt = snack(a + 1, b1, b2, 1) + A[a];
if (b1 <= b2) {
rt = MAX(rt, snack(a, b1 + 1, b2, 1)) + B[b1];
rt = MAX(rt, snack(a, b1, b2 - 1, 1)) + B[b2];
}
}
return rt;
}
/*
int snack(int a, int b1, int b2, char c) {//c가 0이면 A 선택, 1이면 B1 선택 2이면, B2 선택
if (a > N) return 0;
if (b1 > b2) return -987654321;
int& rt = cache[a][b1][b2];
if (rt != -1) return rt;
if (c == 0) {
// 고르는 경우
rt = snack(a + 2, b1, b2, 0); //다음것이 a
rt = MAX(rt, snack(a + 1, b1 + 1, b2, 1)); // 다음것이 b1
rt = MAX(rt, snack(a + 1, b1, b2 - 1, 2)); // 다음것이 b2
rt += A[a];
// 안고르는 경우
rt = MAX(rt, snack(a + 1, b1, b2, 0)); // 다음것이 a
rt = MAX(rt, snack(a + 1, b1, b2, 1)); // 다음것이 b1
rt = MAX(rt, snack(a + 1, b1, b2, 2)); // 다음것이 b2
}
else if (c == 1){
// 고르는 경우
rt = snack(a + 1, b1 + 1, b2, 0); // 다음것이 a
rt = MAX(rt, snack(a, b1 + 2, b2, 1)); // 다음것이 b1
rt = MAX(rt, snack(a, b1 + 1, b2 - 1, 2)); // 다음것이 b2
rt += B[b1];
// 안고르는 경우
rt = MAX(rt, snack(a, b1 + 1, b2, 0)); // 다음것이 a
rt = MAX(rt, snack(a, b1 + 1, b2, 1)); // 다음것이 b1
rt = MAX(rt, snack(a, b1 + 1, b2, 2)); // 다음것이 b2
}
else {
// 고르는 경우
rt = snack(a + 1, b1, b2 - 1, 0); // 다음것이 a
rt = MAX(rt, snack(a, b1 + 1, b2 - 1, 1)); // 다음것이 b1
rt = MAX(rt, snack(a, b1, b2 - 2, 2)); // 다음것이 b2
rt += B[b2];
// 안고르는 경우
rt = MAX(rt, snack(a, b1, b2 - 1, 0)); // 다음것이 a
rt = MAX(rt, snack(a, b1, b2 - 1, 1)); // 다음것이 b1
rt = MAX(rt, snack(a, b1, b2 - 1, 2)); // 다음것이 b2
}
//cout << a << ' ' << b << ' ' << c << " " << rt << '\n';
return rt;
}
*/
int main(int argc, char** argv) {
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case) {
A[0] = B[0] = 0;
cin >> N;
for (int i = 1; i <= N; ++i)
cin >> A[i];
cin >> M;
for (int i = 1; i <= M; ++i)
cin >> B[i];
sort(&B[1], &B[M]);
memset(cache, -1, sizeof(cache));
int a = MAX(snack(1, 1, M, 0), snack(1, 1, M, 1));
cout << '#' << test_case << ' ' << a << '\n';
}
return 0;
}
I2RlZmluZSBfQ1JUX1NFQ1VSRV9OT19XQVJOSU5HUwojZGVmaW5lIE1BWChBLCBCKSBBID4gQiA/IEEgOiBCCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxtZW1vcnkuaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgTiwgTTsKaW50IEFbMzAwMV07CmludCBCWzEwMV07CmludCBjYWNoZVs2XVs0XVs0XVsyXTsKCmludCBzbmFjayhpbnQgYSwgaW50IGIxLCBpbnQgYjIsIGJvb2wgc2tpcCkgewoKCWludCYgcnQgPSBjYWNoZVthXVtiMV1bYjJdW3NraXBdOwoJaWYgKHJ0ICE9IC0xKSByZXR1cm4gcnQ7CgoJY291dCA8PCBhIDw8ICcgJyA8PCBiMSA8PCAnICcgPDwgYjIgPDwgJyAnIDw8IHNraXAgPDwgJ1xuJzsKCglydCA9IDA7CglpZiAoc2tpcCkgewoJCWlmIChhIDwgTikgcnQgPSBzbmFjayhhICsgMSwgYjEsIGIyLCAwKTsKCQlpZiAoYjEgPD0gYjIpIHsKCQkJcnQgPSBNQVgocnQsIHNuYWNrKGEsIGIxICsgMSwgYjIsIDApKTsKCQkJcnQgPSBNQVgocnQsIHNuYWNrKGEsIGIxLCBiMiAtIDEsIDApKTsKCQl9Cgl9CgkKCWVsc2UgewoJCWlmIChhIDwgTikgcnQgPSBzbmFjayhhICsgMSwgYjEsIGIyLCAxKSArIEFbYV07CgkJaWYgKGIxIDw9IGIyKSB7CgkJCXJ0ID0gTUFYKHJ0LCBzbmFjayhhLCBiMSArIDEsIGIyLCAxKSkgKyBCW2IxXTsKCQkJcnQgPSBNQVgocnQsIHNuYWNrKGEsIGIxLCBiMiAtIDEsIDEpKSArIEJbYjJdOwoJCX0KCX0KCXJldHVybiBydDsKfQoKLyoKaW50IHNuYWNrKGludCBhLCBpbnQgYjEsIGludCBiMiwgY2hhciBjKSB7Ly9j6rCAIDDsnbTrqbQgQSDshKDtg50sIDHsnbTrqbQgQjEg7ISg7YOdIDLsnbTrqbQsIEIyIOyEoO2DnQoKCWlmIChhID4gTikgcmV0dXJuIDA7CglpZiAoYjEgPiBiMikgcmV0dXJuIC05ODc2NTQzMjE7CgoJaW50JiBydCA9IGNhY2hlW2FdW2IxXVtiMl07CglpZiAocnQgIT0gLTEpIHJldHVybiBydDsKCglpZiAoYyA9PSAwKSB7CgkJLy8g6rOg66W064qUIOqyveyasAoJCXJ0ID0gc25hY2soYSArIDIsIGIxLCBiMiwgMCk7IC8v64uk7J2M6rKD7J20IGEKCQlydCA9IE1BWChydCwgc25hY2soYSArIDEsIGIxICsgMSwgYjIsIDEpKTsgLy8g64uk7J2M6rKD7J20IGIxCgkJcnQgPSBNQVgocnQsIHNuYWNrKGEgKyAxLCBiMSwgYjIgLSAxLCAyKSk7IC8vIOuLpOydjOqyg+ydtCBiMgoJCXJ0ICs9IEFbYV07CgoJCS8vIOyViOqzoOultOuKlCDqsr3smrAKCQlydCA9IE1BWChydCwgc25hY2soYSArIDEsIGIxLCBiMiwgMCkpOyAvLyDri6TsnYzqsoPsnbQgYQoJCXJ0ID0gTUFYKHJ0LCBzbmFjayhhICsgMSwgYjEsIGIyLCAxKSk7IC8vIOuLpOydjOqyg+ydtCBiMQoJCXJ0ID0gTUFYKHJ0LCBzbmFjayhhICsgMSwgYjEsIGIyLCAyKSk7IC8vIOuLpOydjOqyg+ydtCBiMgoJfQoKCWVsc2UgaWYgKGMgPT0gMSl7CgkJLy8g6rOg66W064qUIOqyveyasAoJCXJ0ID0gc25hY2soYSArIDEsIGIxICsgMSwgYjIsIDApOyAvLyDri6TsnYzqsoPsnbQgYQoJCXJ0ID0gTUFYKHJ0LCBzbmFjayhhLCBiMSArIDIsIGIyLCAxKSk7IC8vIOuLpOydjOqyg+ydtCBiMQoJCXJ0ID0gTUFYKHJ0LCBzbmFjayhhLCBiMSArIDEsIGIyIC0gMSwgMikpOyAvLyDri6TsnYzqsoPsnbQgYjIKCQlydCArPSBCW2IxXTsKCQkKCQkvLyDslYjqs6DrpbTripQg6rK97JqwCgkJcnQgPSBNQVgocnQsIHNuYWNrKGEsIGIxICsgMSwgYjIsIDApKTsgLy8g64uk7J2M6rKD7J20IGEKCQlydCA9IE1BWChydCwgc25hY2soYSwgYjEgKyAxLCBiMiwgMSkpOyAvLyDri6TsnYzqsoPsnbQgYjEKCQlydCA9IE1BWChydCwgc25hY2soYSwgYjEgKyAxLCBiMiwgMikpOyAvLyDri6TsnYzqsoPsnbQgYjIKCX0KCgllbHNlIHsKCQkvLyDqs6DrpbTripQg6rK97JqwCgkJcnQgPSBzbmFjayhhICsgMSwgYjEsIGIyIC0gMSwgMCk7IC8vIOuLpOydjOqyg+ydtCBhCgkJcnQgPSBNQVgocnQsIHNuYWNrKGEsIGIxICsgMSwgYjIgLSAxLCAxKSk7IC8vIOuLpOydjOqyg+ydtCBiMQoJCXJ0ID0gTUFYKHJ0LCBzbmFjayhhLCBiMSwgYjIgLSAyLCAyKSk7IC8vIOuLpOydjOqyg+ydtCBiMgoJCXJ0ICs9IEJbYjJdOwoKCQkvLyDslYjqs6DrpbTripQg6rK97JqwCgkJcnQgPSBNQVgocnQsIHNuYWNrKGEsIGIxLCBiMiAtIDEsIDApKTsgLy8g64uk7J2M6rKD7J20IGEKCQlydCA9IE1BWChydCwgc25hY2soYSwgYjEsIGIyIC0gMSwgMSkpOyAvLyDri6TsnYzqsoPsnbQgYjEKCQlydCA9IE1BWChydCwgc25hY2soYSwgYjEsIGIyIC0gMSwgMikpOyAvLyDri6TsnYzqsoPsnbQgYjIKCX0KCgkvL2NvdXQgPDwgYSA8PCAnICcgPDwgYiA8PCAnICcgPDwgYyA8PCAiICAgIiA8PCBydCA8PCAnXG4nOwoKCXJldHVybiBydDsKfQoqLwppbnQgbWFpbihpbnQgYXJnYywgY2hhcioqIGFyZ3YpIHsKCgljaW4udGllKE5VTEwpOwoJY291dC50aWUoTlVMTCk7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCglpbnQgdGVzdF9jYXNlOwoJaW50IFQ7CgoJY2luID4+IFQ7CgoJZm9yICh0ZXN0X2Nhc2UgPSAxOyB0ZXN0X2Nhc2UgPD0gVDsgKyt0ZXN0X2Nhc2UpIHsKCgkJQVswXSA9IEJbMF0gPSAwOwoKCQljaW4gPj4gTjsKCQlmb3IgKGludCBpID0gMTsgaSA8PSBOOyArK2kpCgkJCWNpbiA+PiBBW2ldOwoKCQljaW4gPj4gTTsKCQlmb3IgKGludCBpID0gMTsgaSA8PSBNOyArK2kpCgkJCWNpbiA+PiBCW2ldOwoKCQlzb3J0KCZCWzFdLCAmQltNXSk7CgoJCW1lbXNldChjYWNoZSwgLTEsIHNpemVvZihjYWNoZSkpOwoKCQlpbnQgYSA9IE1BWChzbmFjaygxLCAxLCBNLCAwKSwgc25hY2soMSwgMSwgTSwgMSkpOwoKCQljb3V0IDw8ICcjJyA8PCB0ZXN0X2Nhc2UgPDwgJyAnIDw8IGEgPDwgJ1xuJzsKCX0KCglyZXR1cm4gMDsKfQ==