Gully cricket

2.5

2 votes
Problem

Gaganjyot loves cricket and is the king of your gully as he is the only boy who has a bat in your gully. Every day he scores the same m amount of runs, and if you score more than him then he bans you for next d days. Your final score is the sum of scores that you can actually make ie. on days that you play and are not banned. You are given n scores that you can make, but if your ith score is greater than m, then score on the next successive d days will not be counted on your final score as you will be banned. You can arrange the n scores in any order and you have to tell the maximum final score you can make.

Input constraints:

1dn105

0m109

Scores:0a[i]109

 

Input format:

The first line contains 3 space-separated integers: n no of scores, d no of days of the ban, m the score by Gaganjyot. The second line contains n space-separated integers a[i] the scores that you can make.

 

Output format:

The only line of output contains the maximum score that you can make with given constraints.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The scores can be arranged like - 23, 5, 8, 10, 15.

Then final score would be 23+10+15 (5, 8, were scores of banned days).

Editor Image

?