All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Aryan hates shopping
Tag(s):

Easy

Problem
Editorial
Analytics

Aryan hates shopping but he has to go with his mom to supermarket.There his mom is keeping things in basket but when she realizes the cost is getting over the budget,she tells his son to remove X items with maximum price and if basket contains less than X items then he removes all the items.She continues doing the shopping in similar manner.Now,after sometime,his mom stops and finally goes for billing.Now, Aryan's task is how much money she has to pay to shopkeeper.

You will be given an Array of size N where A[i] will represent the price of ith item.But if A[i]=0 then you have to remove X items present in basket with maximum price. If there are more than one occurence of item with same price then each item will be counted in removal of X items. For example if the items are priced as = {2,3,3,4,4,4} and X=4 then after removal,you will be left with {2,3}.


Input :-
First Line contains two integers - N & X.

Then N integers,where  A[i] will represent the price of ith item.

Constraint :-
1<=N<=100000
0<=A[i]<=1018

1<=X<=20

Output :-

Print one integer which is total money she she has to pay to shopkeeper.

SAMPLE INPUT
15 6
7 8 2 17 9 0 2 3 8 8 8 1 4 0 1
SAMPLE OUTPUT
2
Explanation

When first zero occurs then Aryan haa to  remove 6 items but there are only 5 items in basket so he removes all the items. When second zero occurs,he removes  6 items out of 7 items present in basket with maximum price. So,at last total price will be 1+1=2.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?