Candy Shop :
Difficulty Level : Medium
Submissions : 414
Asked In :
Marks :10
: 8 | : 0
Jack loves candles, and he goes to the market to buy some. There are $$$K$$$ different flavors of candles available in the market, and he wants to buy candles of all flavors.
Also, there are $$$N$$$ types of candy combos available in the market. Each candy combo having some cost $$$C$$$ contains candles of one or more flavors. Help Jack to buy candy combos in such a way that he will have all the flavors at the end and will have to incur the minimum cost in doing so.
You are given $$$-$$$
$$$1.$$$ An Integer array $$$Cost[$$$ $$$]$$$ having the cost of all the candy combos available in the market.
$$$2.$$$ An integer $$$K$$$ denoting the number of different candy flavors available in the market.
$$$3.$$$ An integer $$$N$$$ denoting the different types of candy combos available in the market.
$$$4.$$$ An array of $$$N$$$ binary strings denoting the availability of various candy flavors in a candy combo. In each string, denoting a single combo, if the $$$i^{th}$$$ character is $$$1$$$ that means it contains the $$$i^{th}$$$ flavor of candy otherwise not.
Your task is to return the minimum cost required for buying combos such that Jack will have all the flavors of candies in the end.
$$$\textbf{Note:}$$$ If you can't get all the K flavors at the end, you need to return $$$-1$$$.
$$$\textbf{Constraint}$$$
$$$1 \le N \le 10^{4}$$$
$$$1 \le K \le 31$$$
$$$1 \le Cost_{i} \le 10^{9}$$$
The first line contains two integers, $$$N$$$ and $$$K$$$, denoting the different types of candy combos and the number of different candy flavors respectively available in the market.
The second line contains an array of $$$N$$$ binary strings of length $$$K$$$.
The second line contains an array of $$$N$$$ integers denoting the cost of all candy combos.
Return the minimum cost required for buying combos such that Jack will have all the flavors of candles in the end and $$$-1$$$ If not possible.
5 4 1010 0100 0001 1111 1011 5 5 5 10 2
7
For the sample case, there are multiple ways to buy combos -
If he buys the 1, 2nd, and 3rd combo, he will get all the flavours at a total cost of 15.
If he buys only the 4th combo, he will still get all the flavours at a total cost of 10.
If he buys the 2nd and 5th combo, he will get all the flavours at a total cost of 7.
