Problem related to set partitioning
Let $OPT[t, x]$ be the maximum value of $\sum_{j=1}^t  b_j^{i_j}$  that can be attained by selecting one element $(a_j^{i_j}, a_j^{i_j})$ from each of the first $t$ sets with the constraint that $\sum_{j=1}^i  a_j^{i_j} \ge x$.
If the constraint cannot be satisfied, let $OPT[t, x] = -\infty$.

According to the above definition we have $OPT[0, 0] = 0$ and $OPT[0, x] = -\infty$ for $x &gt; 0$.

For $t&gt;0$ we have:
$$
OPT[t,x] = \max_{i=1, \dots, n} \left( b_t^i + OPT[t-1, \max\{x-a_t^i, 0\}] \right).
$$

The answer to your problem is "yes" if and only if $OPT[p, k] \ge k$.

Since there are $O(p \cdot k)$ subproblems, each of which can be solved in $O(n)$ time, the overall time complexity of this algorithm is $O(p \cdot k \cdot n)$.

To show that your problem is NP-hard, you can notice that it is a generalization of partition problem: given a set $S = \{x_1, \dots, x_m\}$ of $m$ non-negative integers, decide whether there is a subset $S'$ of $S$ such that $\sum_{x \in S'} x = \frac{1}{2} \sum_{x \in S} x$.

To see this, define $n=2$, $p=m$, $A_j = \{ (x_j, 0), (0, x_j) \}$, and $k = \frac{1}{2} \sum_{x \in S} x$.