There are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get at least one dish of his choice. What is the minimum number of different type of dishes we can order?
Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row.
n = 6 k = 7
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 1 0 0
0 0 1 0 0 1 0
0 0 0 1 0 0 1
Output
3
Explanation
Take dish number 5,6,7.
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.