Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1
A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \epsilon})$-algorithm is known.

For this we'll use the result that MAXCONV can be solved in $\mathcal{O}(n^{2 - \epsilon})$ iff MAXCONV UPPERBOUND can be solved in $\mathcal{O}(n^{2 - \epsilon})$ (reference: "On Problems Equivalent to (min,+)-Convolution", ICALP 2017)

To show this, first note that we may drop the requirement that the arrays are sorted. To show this, take arbitrary values $b_{i}[j]$, set $V = 2 \max_{i, j} |b_{i}[j]|$, and set $a_{i}[j] = b_{i}[j] + Vj$. Now $a_{i}[j+1] - a_{i}[j] = b_{i}[j+1] - b_{i}[j] + V \geq 0 \geq 0$, and the answer for $a$s is exactly $(k+1)V$ more than the answer for $b$s.

In a MAXCONV UPPERBOUND instance $(a[i])_{i = 0}^{n-1}, (b[i])_{i = 0}^{n-1}, (c[i])_{i = 0}^{n-1}$ we are asked if for all $k$ we have $\max_{i+j = k} a[i] + b[j] \leq c[k]$. To reduce it to our problem, set $a_{1}[j+1] = a[j]$, $a_{2}[j+1] = b[j]$ and $a_{3}[j] = -c[n-j]$. Further set $a_{1}[n+1] = a_{2}[n+1] = a_{3}[n+1] = -\infty$. Now the answer is positive if and only if at least one of the upper bounds doesn't hold: if the answer is positive, then $a_{1}[x] + a_{2}[y] + a_{3}[z] &gt; 0$ for some $x + y + z = n+2$, hence $a[x-1] + b[y-1] &gt; c[(x-1)+(y-1)]$ and the upper bound for $k = x+y-2$ doesn't hold. Similarly if $a[i] + b[j] &gt; c[i+j]$, we have $a_{1}[i+1] + a_{2}[j+1] + a_{3}[n+2 - (i+1) - (j+1)] = a[i] + b[j] - c[i+j] &gt; 0$.