I am trying to know whether the following problem is NP-hard:Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$.The problem is to select a subset of numbers $S$ among the set $\{a_1,b_1,a_2,b_2,..., a_N, b_N\}$ such that it maximizes the sum of the values of the $S$.The are two constraints:For each pair $i,\; (i=1,...,N)$ you cannot select $a_i \text{ AND } b_i$ (either $a_i$, or $b_i$, or none, but never both)The weight of selecting the number $a_i$ is 1, and the weight of selecting the number $b_i$ is 2 (for all $i=1,...,N$). The sum of the weights of all the numbers selected in $S$ cannot exceed $k$.Is this problem NP-hard?
Problem related to the Knapsack problem: Is it NP-hard?
complexity theory;np hard;knapsack problems