All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Flat Earth Society
/
No tags
Problem
Editorial
Analytics

Abhishek Sinha like everyone else was a firm believer of Sphere Earth, believing what school has taught and not trusting their own insights.
Once Sir Notsocool Hawkins quoted "Everything in life doesn't need to be hard and complex, sometimes it is simple and flat, just like our Planet".

After getting motivated, Abhishek Sinha establishes 'Flat Earth Society' and to join the society, one must solve the following problem:

Given an array A consisting of N integers. In a single step player can choose an element of the array (let's denote it ak) and delete it, at that all elements equal to ak + 1,ak + 2......ak + R and ak - 1,ak - 2.....ak - L also must be deleted from the array. This step will add ak points to player. Player can perform any number of steps.

Find maximum points which can be obtained.

 

Input Format

First line contains T testcases.

Each Testcase contains three integers N, and R, where N is number of elements in array, and use of L and R has been explained in Problem statement.

The next line contains N integers denoting elements of array A.

Output Format

A single line for each test case, output a single integer denoting the maximum points possible..

Constraints

1 <= T <= 100

1 <= N, L, R <= 10^5

1<= ak <=10^5

SAMPLE INPUT
1
9 1 1
1 2 1 3 2 2 2 2 3
SAMPLE OUTPUT
10
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?