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...

## This Problem was Asked in

Challenge Name

3 Address Code - On site Hackathon - Finals

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Game Theory
• Algorithms > Dynamic Programming
• Math > Number Theory
• Math > Probablity