If you are given an $m*n$ matrix $A$ where $m\ge1$ and $n\ge1$, and target $k\ge1$, how would you determine the total number of combinations from the matrix that sum to less than or equal to k such that at least 1 entry from every row must be present in the linear combination?
For example, suppose you wanted to find the number of linear combinations that sum to no more than 10 in the following matrix:
$$\begin{pmatrix} 2&3\\ 4&0\\ 2&3\\ 1&2 \end{pmatrix}$$
Because every row must be present in the linear combination, we must find the combinations that sum to no more than 6 (in other words, $m_2n_1$ is by default included in the linear combination. Our answer is 4:
$1*m_1n_1 + 1*m_3n_1 + 1*m_4n_2 = 6$
$1*m_1n_1 + 1*m_3n_1 + 1*m_4n_1 = 5$
$1*m_1n_2 + 1*m_3n_1 + 1*m_4n_1 = 6$
$1*m_1n_1 + 1*m_3n_2 + 1*m_4n_1 = 6$