All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Balls in Boxes
Tag(s):

Algorithms, Dynamic Programming

Problem
Editorial
Analytics

Misha loves to collect sets of colored balls. She saw \(N\) boxes kept in a store. Each box has a set of \(10\) distinct colored balls. The colors are numbered from 1 to 10. Each box has a cost associated with it. She is required to spend the minimum amount of money to buy the boxes such that she has maximum distinct colored balls in the end.

Input format

  • First line: \(N\) denoting the number of boxes kept in a store
  • Next \(N\) lines: An integer denoting the cost of the box \(C_{i}\) and a binary string \(S_{i}\) of length \(10\). If the \(j^{th}\) character of the string \(S_i\) is \(1\) then it means that there exists a ball of color \(j\) in that box.

Output format

Print the minimum amount of money that she has to spend.

Constraints

\(1 \le N \le 10^{4}\)

\(1 \le C_{i} \le 10^{9}\)

\(|S_{i}| = 10\)

SAMPLE INPUT
3
20 0110100110
10 1001000101
9 1111111111
SAMPLE OUTPUT
9
Explanation

If we take the last box, we will get all the 10 distinct colored balls thereby incurring a cost of 9 units. Hence, the answer is 9.

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, 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, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Johnson & Johnson

Challenge Name

3 Address Code - On site Hackathon - Finals

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?