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 ≤ 106) and K (1 ≤ K ≤ 106), the number of radars and the minimum distance between two radars, respectively. The next line will contain N space separated positive integers, ranging from 1 to 106, indicating the positions of the radars, in a non-decreasing order. The last line will contain N space separated positive integers, ranging from 1 to 103, indicating the profit of each radar.
For each test case, output a single line, the answer for the problem.
|Sample Input||Sample Output|
1 2 3
2 5 3
1 5 10 15 17
5 20 10 15 25