최대 획득 점수

Charles는 Crowdsource 작업 이벤트에 참가하고 있으며, 그곳에서 최대한 많은 점수를 얻고 싶어 한다! Crowdsource 작업에는 Audio Validation Task와 Image Labeler Task의 두 가지가 있다. 각 작업은 질문 목록으로 구성된다. Charles에게 두 작업을 나타내는 두 배열($\mathbf{A}$와 $\mathbf{B}$)이 주어진다. 배열의 각 원소는 Charles가 해당 질문에 답하여 얻을 점수를 나타낸다.

Charles는 두 작업에서 한 번에 하나씩, 총 $\mathbf{K}$개의 질문에 답할 수 있다. 각 단계에서 아직 답하지 않은 질문이 남아 있는 작업, 즉 두 배열 중 하나를 선택할 수 있다. 그런 다음 이 작업에 남아 있는 질문 목록에서 첫 질문이나 마지막 질문 중 하나에 답할 수 있다. 질문에 답하면 해당 점수를 얻고, 답한 질문은 작업에서 제거된다.

Charles가 가능한 최대 점수를 얻도록 질문을 선택하는 것을 도와줄 수 있는가?

제한

시간 제한: 30초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 6000$. $1 \le \mathbf{M} \le 6000$. 모든 $i$에 대해 $1 \le \mathbf{A_i}, \mathbf{B_i} \le 10^9$. $1 \le \mathbf{K} \le \mathbf{N}+\mathbf{M}$.

테스트 세트 1

$1 \le \mathbf{K} \le 30$.

테스트 세트 2

$1 \le \mathbf{K} \le 3000$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 첫 번째 배열의 원소 수를 나타내는 정수 $\mathbf{N}$가 주어진다. 각 테스트 케이스의 둘째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{A_1}, \mathbf{A_2}, \dots, \mathbf{A_N}$가 주어진다. $\mathbf{A_i}$는 Audio Validation Task의 $i$번째 질문에 답하여 얻는 점수를 나타낸다. 각 테스트 케이스의 셋째 줄에는 두 번째 배열의 원소 수를 나타내는 정수 $\mathbf{M}$가 주어진다. 각 테스트 케이스의 넷째 줄에는 $\mathbf{M}$개의 정수 $\mathbf{B_1}, \mathbf{B_2}, \dots, \mathbf{B_M}$가 주어진다. $\mathbf{B_i}$는 Image Labeler Task의 $i$번째 질문에 답하여 얻는 점수를 나타낸다. 각 테스트 케이스의 다섯째 줄에는 위에서 설명한 과정을 사용해 두 배열에서 총 몇 개의 원소를 선택해야 하는지를 나타내는 정수 $\mathbf{K}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Charles가 이 테스트 케이스에서 얻을 수 있는 최대 점수이다.

예제 케이스 #1에서 Charles는 $5$개의 질문에 답할 수 있다. 첫 번째 배열에서 첫 질문과 마지막 질문을 선택하면 $(3+2)$점을 얻는다. 두 번째 배열에서 처음 두 질문과 마지막 질문을 선택하면 $(2+8+9)$점을 얻는다. 따라서 이 $5$개의 질문에 답하면 Charles는 $((3+2)+(2+8+9)) = 24$점을 얻는다. 이는 Charles가 이 테스트 케이스에서 얻을 수 있는 최대 점수이다. 최적이 아닌 선택의 예로는 첫 번째 배열에서 마지막 두 원소를 선택하고, 두 번째 배열에서 첫 원소와 마지막 두 원소를 선택하는 것이 있다. 이렇게 하면 $((1+2)+(2+1+9)) = 15$점을 얻었을 것이다.

예제 케이스 #2에서 Charles는 $6$개의 질문에 답할 수 있다. 첫 번째 배열에서 처음 두 질문을 선택하면 $(1+100)$점을 얻는다. 두 번째 배열에서 처음 세 질문과 마지막 질문을 선택하면 $(15+10+12+10)$점을 얻는다. 따라서 이 $6$개의 질문을 선택하면 Charles는 $((1+100)+(15+10+12+10)) = 148$점을 얻으며, 이는 이 케이스의 최댓값이다.