Maximum profit HackerEarth Question

Maximum profit

Max. score: 100

In a game, you have the following:

• Pile of N coins
• List of restricted coins

Conditions

• A player can choose at most K coins one by one.
• They cannot choose a value that is present in the list of restricted coins.
• At the beginning of the game, the list of restricted coins is empty. Whenever a player selects a coin, it is added to their profit and also appended in the list of restricted coins.
• A player can discard a coin even if it is not present in the list of restricted coins.

Task

Your task is to determine the maximum profit that a player can make.

Input format

• The first line contains T denoting the number of test cases.
• In each test case:
  • The first line contains:
    • Two space-separated integers
    • Number of coins N
    • Maximum number of coins that a player can take K
  • The second line contains N space-seperated integers denoting the value of the coins.

Output format

• For each test case, print a single line denoting the maximum profit a player can make.

Constraints

• $1\le T\le 20000$
• $1\le N\le 200000$
• 1 <= Value of Coin <= 1e9
• Sum of N over all test cases will not exceed 200000

SAMPLE INPUT

 

1
5 4
2 3 3 2 2

SAMPLE OUTPUT

 

5

Explanation

Player can choose 2 and 3. He can not choose any number twice as it will be added to restricted coin list.

2 moves will be wasted as he has no other option so profit=2+3=5.

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Score is assigned if any testcase passes.

Allowed Languages:Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic