Select a subset of the columns in $3\times n$ matrix, is it NP-hard? I want to know if this problem is NP-hard? 

The problem: Given a non-negative integer-valued matrix of size $3\times n$ of the form 

$$
\begin{bmatrix}
a_1 &amp; \ldots &amp; a_n\\
b_1 &amp; \ldots &amp; b_n\\
a_1b_1 &amp; \ldots &amp; a_nb_n\\
\end{bmatrix},
$$

where $a_i,b_i$ are non-negative integers. Given four non-negative integer numbers $b&lt;n$, $c_1$, $c_2$ and $c_3$. 

The goal: Find a subset of the columns of cardinality at most $b$ such that (i) the sum of the first row over the subset of the columns is greater than $c_1$, (ii) the sum of the second row over the subset of the columns is greater than $c_2$ and (iii) the sum of the third row over the subset of the columns is less than $c_3$. Return no if no such subset exists. That is to say, is there exists a set $S$ of cardinality at most $b&lt;n$ such that:

$$
\sum_{i\in S}a_i\geq c_1,\\
\sum_{i\in S}b_i\geq c_2,\\
\sum_{i\in S}a_ib_i\leq c_3,
$$

How to show that this problem is NP-hard?



Attempt:

Here is a "similar" NP-hard problem that I asked. This problem has as instance $(n,b,c,\mathbf{A})$ where $\mathbf{A}$ is given by 
$$
\begin{bmatrix}
x_1 &amp; \ldots &amp; x_n\\
y_1 &amp; \ldots &amp; y_n\\
\end{bmatrix},
$$
I tried to reduce the previous problem to the new one as follows: choose $c_1=c_2=c$ and choose $c_3$ very big and create the matrix as follows:

$$
\begin{bmatrix}
x_1 &amp; \ldots &amp; x_n\\
y_1 &amp; \ldots &amp; y_n\\
x_1y_1 &amp; \ldots &amp; x_ny_n\\
\end{bmatrix},
$$
Your problem is NP-complete, indeed. You can, e.g., reduce PARTITION to your problem. If you want to know if there is a subset of the set $\{d_1,\ldots,d_k\}$ that sums up to exactly $D := \frac{1}{2} \sum_{i=1}^k d_i$, you can use your problem by setting $b_i := 1$ and $a_i := d_i$ for all $i$ and by setting $c_1 := D$, $c_2 = 0$, and $c_3 := D$ as well as $b := n-1$.