Minimum Stores to Fulfill Item Requirements

In this problem, you are given a 2D matrix that represents the availability of various items in different stores, and a list of requirements indicating the minimum quantity needed for each item. You are required to determine the minimum number of stores you must visit such that the total supply meets or exceeds the requirements for every item. If it is impossible to satisfy the requirements, output -1.

The supplies available at store i are represented by the i-th row of the matrix. For each item (column), you need to sum the supplies from the chosen stores and compare it with the required quantity. Formally, you need to find the smallest subset \(S \subseteq \{0, 1, \ldots, n-1\}\) such that for every item \(j\):

\(\sum_{i \in S} matrix[i][j] \ge requirements[j]\)

inputFormat

The first line contains two integers n (the number of stores) and m (the number of items). The next n lines each contain m integers representing the number of each item available in that store. The last line contains m integers representing the required quantity for each item.

outputFormat

Output a single integer, the minimum number of stores needed to meet the requirements. If it is impossible to meet the requirements, output -1.## sample

3 3
2 0 1
1 3 1
0 3 4
1 4 2

2