All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Balls in Boxes
/

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?