The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be integer parameters. Assume that for all $i \in [k]$ it holds that $a^i_1 \leq a^i_2 \leq \ldots \leq a^i_n$. The goal is to find $r_1,\ldots,r_k \in [n]$ (possibly with repetition) such that
$$\sum_{i \in [k]} \sum_{j \in [r_i]} a^i_j \leq U, ~~~\sum_{i \in [k]} \sum_{j \in [r_i]} a^i_{n-j+1} \geq L.$$
In words, we take $k$ prefixes, one for each set, according to a sorted way, and we want that the total sum of the prefixes to be upper bounded by $U$; at the same time, we want that the total sum of the corresponding suffixes (e.g., the corresponding suffix of $a^i_1,a^i_2$ is $a^i_n,a^i_{n-1}$) to be lower bounded by $L$.
Question: Is this problem NP-Hard?
Wlog assume $r_1 \leq r_2 \leq \ldots \leq r_k$.
We can prove that if there is a solution then there is a solution with $r_k \leq r_1 + 1$. Indeed, if $r_k > r_1 + 1$, then replacing $r_k$ with $r_k - 1$ and $r_1$ with $r_1 + 1$ we reduce the left sum by $a_{r_k} - a_{r_1 + 1} \geq 0$, increase the right sum by $a_{n - r_1 - 1} - a_{n - r_k} \geq 0$, thus still getting solution. As such replacement reduces $\sum_{p, q} |r_p - r_q|$, we can't do it infinitely, at after some replacements we will find solution with $r_k \leq r_1 + 1$.
Now, there are only polynomial (in $n$) such variants: we have $n$ variants for $r_1$ and for each of them at most $n$ variants for $j$ s.t. $r_j = r_{j - 1} + 1$. Checking all of them, we find solution or prove that there is no solution. It can be significantly sped up by binary search, but this is good enough to show that this problem is in P.
So, unless P = NP, this problem is not NP-hard.