URI Online Judge | 1689
# Radars

**Timelimit: 1 second**

By Rodrigo Rusa, ICMC - USP Brazil

Antonio, mayor of Little River, is willing to deploy radars on the main road of the city.

For this he has a list of possible points, where the radars that can be installed. Each radar has a profit associated. It is known that the distance between two radars can not be less than *K*, according to the traffic legislation.

Given the list of points and their profits, your task is to help Antonio to choose the points to install the radars so that the profit is maximized. Print the maximum profit!

For instance, take the radars at positions 1, 2 and 3, with profits 2, 5 and 3, respectively. If *K* equals 2, one optimal answer would be to choose radars at positions 1 and 3, summing up 5 of profit.

The first line will contain a number **T** (**1** ≤ **T** ≤ **100**), indicating how many test cases will follow.

For each test case, the first line will contain **N** (**1** ≤ **N** ≤ **10 ^{6}**) and

For each test case, output a single line, the answer for the problem.

Sample Input | Sample Output |

3 2 1 1 1 3 2 3 2 1 2 3 2 5 3 5 5 1 5 10 15 17 5 20 10 15 25 |
3 5 55 |