All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Toy Box
Tag(s):

Algorithms, Easy, Greedy algorithm

Problem
Editorial
Analytics

You have \(N\) toys and \(M\) toy boxes. Initially all boxes are empty, and each box can contain only one toy. Each toy has a price and a box number assigned to it. If you want to choose a toy, you must put it in its assigned box, and of course that box can’t be used for any other toys. You need choose some toys (with their boxes) such that summation of their price is maximized.

Input Format

First line contains two integers \(N\) and \(M\), they are number of toys and number of toy boxes repectively. Each of the next \(N\) lines will contain information about each toy \(P_{i}\) and \(B_{i}\), where \(P_{i}\) is the price of i’th toy and \(B_{i}\) is the box number assigned to it.

\(1 <= N, M <= 100 \)

\(1 <= B_{i}<= M\)

\(1 <= P_{i}<= 100\)

Output Format

Print one integer, maximum summation of  price of toys that you can choose by following the problem description.

 

SAMPLE INPUT
5 6
3 1
4 2
1 1
2 3
1 6
SAMPLE OUTPUT
10
Explanation

You can get 10 by choosing all toys except the third one. Beacuse it can't be put in first box, which is already carrying first toy.

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

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '19

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?