Surprisingly pass with O(n^4) solution.
Read triangular(N) input.
Compute all tetrahedral(N) subtriangles in O(n^3).
Each subtriangle cost O(n). Could be O(1) by subtracting pre-computed row of sum.
Sort all subtriangles and print first K.

Do we have a case when K is greater then number of possible sums?

I have O(n^3) complexity but only the first case passes (used C++). This is a frustrating problem. It may even timeout in IO!

Lame that this cannot be done in python due to timeout. I did a non-recursive, dynamic programming solution that couldn't get a ton faster, still timeouts on every test case other than the sample.

Can't import numpy python 2.0.....