[Solution] Maximum Gain Round D 2022 | Kick Start 2022 Solution

Problem

Charles is participating in an event of Crowdsource tasks and he is most enthusiastic to gain the maximum points from there! There are two Crowdsource tasks: Audio Validation Task and Image Labeler Task. Each task consists of a list of questions. Charles is given two arrays (A$A$ and B$B$) representing the two tasks. Each element of an array indicates the number of points that Charles will gain by answering the corresponding question.

Charles is allowed to answer K$K$ questions in total, from both tasks, one at a time. At each step, he is allowed to choose a task (that is, choose one of the two arrays) that has remaining unanswered questions. He is then allowed to answer either the first or the last question, from the list of remaining questions of this task. Once he answers the question, he gets the corresponding points and the answered question is removed from the task.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Can you help Charles choose the questions that will give him the maximum possible points?

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
The first line of each test case contains an integer N$N$, which denotes the number of elements in the first array.
The second line of each test case contains N$N$ integers A1,A2,…,AN${\mathbf{A}}_{\mathbf{1}},{\mathbf{A}}_{\mathbf{2}},\dots ,{\mathbf{A}}_{\mathbf{N}}$. Ai${\mathbf{A}}_{\mathbf{i}}$ denotes the points gained for answering the i$i$-th question of Audio Validation Task.

Image Labeler Round D 2022 Solution

Maximum Gain Round D 2022 Solution

Touchbar Typing Round D 2022 Solution

Suspects and Witnesses Round D 2022 Solution

The third line of each test case contains an integer M$M$, which denotes the number of elements in the second array.
The fourth line of each test case contains M$M$ integers B1,B2,…,BM${\mathbf{B}}_{\mathbf{1}},{\mathbf{B}}_{\mathbf{2}},\dots ,{\mathbf{B}}_{\mathbf{M}}$. Bi${\mathbf{B}}_{\mathbf{i}}$ denotes the points gained for answering the i$i$-th question of Image Labeler Task.
The fifth line of each test case contains an integer K$K$, which denotes the number of elements to be selected in total, from both arrays, using the process described above.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the maximum number of points that Charles can gain in this test case.

Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤N≤6000$1\le \mathbf{N}\le 6000$.
1≤M≤6000$1\le \mathbf{M}\le 6000$.
1≤Ai,Bi≤109$1\le {\mathbf{A}}_{\mathbf{i}},{\mathbf{B}}_{\mathbf{i}}\le {10}^9$, for all i$i$.
1≤K≤N+M$1\le \mathbf{K}\le \mathbf{N}+\mathbf{M}$.

Test Set 1

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

Test Set 2

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