## Attraction

View as PDF

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

Author:
Problem type

You are venturing deep in a run-down factory in search for the rare Zusniesium metal, and at last you have found some. Specifically, there are pieces of Zusniesium lined up equidistantly on a conveyor belt, on positions we can label from to . There are also fixed and deactivated attractors located at distinct positions underneath the conveyor belt. Once activated, any piece of Zusniesium will be attracted to the closest attractor, provided that the closest attractor is unique. Luckily, you have brought removable attractors of your own which you may attach to distinct positions where there is no pre-existing attractor. After activating all attractors simultaneously, any piece of Zusniesium attracted to one of your own attractors is yours to keep. Please write a program to find the maximum number of Zusniesium pieces you can take home, provided that you are allowed to attach at most of your own attractors before activating all the attractors. 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 next lines will describe the test cases.

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

The second line of each test case contains distinct integers , the positions of the fixed attractors.

#### Output Specification

For each test case output one integer on its own line, the maximum number of Zusniesium pieces you can take home provided that you are allowed to attach at most of your own attractors before activating all the attractors.

#### Constraints

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

In each test case, all are pairwise distinct.

The sum of over all test cases will not exceed .

The sum of over all test cases will not exceed .

#### Sample Input

3
11 2 3
2 10
10 2 5
1 10
6 4 2
5 1 4 3

#### Sample Output

7
8
2

#### Explanation

For the first test case, one possible solution is to place your own attractors on positions and . This will attract the Zusniesium pieces located at positions . Note that the Zusniesium piece at position is not attracted to any attractor, since there is no unique closest attractor. This scenario is illustrated in the diagram above, where circles in red rectangles represent Zusniesium pieces attracted to the fixed attractors, while circles in blue rectangles represent Zusniesium pieces attracted to your own attractors.

For the second test case, one possible solution is to place of your own attractors on positions and . These will attract all the Zusniesium metal from position to position , leaving you with Zusniesium pieces in total. Note that you do not have to use all of your attractors.

For the last test case, the best you can do is place your attractors on the only unoccupied positions, leaving you with Zusniesium pieces in total.