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.