Tag(s):

## Ad-Hoc, Algorithms, Brute-force search, Dijkstra's algorithm, Graph, Medium, Shortest path problem, 簡単-普通

Problem
Editorial
Analytics

There are n different types of objects. You want to buy atleast one instance of each type of object. There are m people , each of them sells one set of objects at a certain price (price is for the set).
Each of these m people sells either nothing or all the objects in the set he has. Information of these m sellers is represented by matrix M of size $m * n$ . if $M_{i,j} = 1$, it means that $i^{th}$ seller has one $j^{th}$ type of object in his set, otherwise $M_{i,j} = 0$ . The $i^{th}$ seller will sell set of all his objects at price $C_i$.
You want to buy at least one object of each type (it is guaranteed that it is always possible to do so). Find the minimal cost needed to pay to achieve it.

$\textbf{Input}$

The first line contains two integers $n, \; m$ separated by space. ($1 \le n \times m \le 500$).

The $(i + 1)^{th}$ ($1 \le i \le m$) line contains $(n + 1)$ integers - $M_{i,1}, \; M_{i,2}, \; M_{i,3}, \dots, M_{i,n}, \; C_i$. ($0 \le M_{i,j} \le 1, 1 \le C_i \le 10^9$).

$\textbf{Output}$

Output the minimal cost you should pay to buy at least one object of each type.

SAMPLE INPUT
3 3
0 1 1 2
1 0 0 3
1 1 1 9

SAMPLE OUTPUT
5

Explanation

Buy from the 1 and 2 seller with cost $2 + 3 = 5$.

Time Limit: 3.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...

## This Problem was Asked in

Challenge Name

January Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures
• Data Structures > Trees
• Math > Number Theory
• Data Structures > Advanced Data Structures
• Data Structures > Disjoint Data Structures

?