All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Flat Earth Society
No tags

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..


1 <= T <= 100

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

1<= ak <=10^5

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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications