## The Heist

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

You are planning a heist on one of the worst museums in the world. You've already planned out the entrance and exit routes (consisting of simply walking in and then walking out), so the only task left is to decide which artifacts to bring home. Specifically, the artifacts of the museum are numbered from to , laid out in a circular hallway so that the artifact is adjacent to the for , and the artifact is adjacent to the first. The artifact has a value of , but being one of the worst museums in the world, could even be negative for some artifacts! Also, if you take more than items in a row, the emergency alarm will be set off and the doors locked, leaving you soon in the hands of the authorities. Given the circumstances, write a program to help you calculate the maximum net value of artifacts you could take from the museum without setting off the alarm. To ensure the integrity of your solution, there may be multiple test cases.

#### Input Specification

The first line contains an integer , the number of test cases.

The first line of each case contains integers and , as described in the statement.

The second line of each case contains integers , the value of the artifact.

#### Output Specification

Output lines, each containing the answer to the corresponding test case.

#### Constraints

For this problem, you will NOT be required to pass the sample case in order to receive points. In addition, you do not have to pass all previous subtasks to earn points for a specific subtask.

The sum of over all test cases will not exceed .

The sum of over all test cases will not exceed .

#### Sample Input

4
5 2
3 1 0 4 5
2 1
-1 -2
4 4
6 1 3 3
9 3
-3 7 -6 1 1 4 2 3 2

#### Sample Output

10
0
13
18

#### Explanation

The diagram above illustrates the optimal solution to the first case, with the chosen artifacts marked in yellow. Note that it is not allowed to choose the artifacts with values , , and together, since that is more than chosen artifacts in a row.

In the second case, it is optimal to take nothing at all. (and maybe find a better museum…)

In the third case, it is optimal to take all artifacts.

The optimal solution to the fourth case is illustrated below, with the chosen artifacts marked in yellow.