Does there exist a way to efficiently solve the following problem?

Given some constant $k$ and several sets of non-negative integers:
$a_0\in\{a_{0,0},a_{0,1},...,a_{0,m_0}\},$
$a_1\in\{a_{1,0},a_{1,1},...,a_{1,m_1}\},$
$ ...,$
$ a_n\in\{a_{n,0},a_{n,1},...,a_{n,m_n}\}$
$\forall i \forall j, 0 \leq a_{i,j} < k$

Find the smallest sum $S = a_0+a_1+...+a_n$ such that $S \geq k$.

I know that the problem is trivial when $k = 0$, but am unsure if there exists an efficient approach when $k > 0$.