You are given $ n$ rows of positive integers of length $ k$ . We define a weight function for every subset of given $ n$ rows as follows – for every $ i = 1, 2, \dots, k$ take the maximum value of $ i$ -th column (), then add up all the maximums.

For example, for $ n = 4$ , $ k = 2$ and rows $ (1, 4), (2, 3), (3, 2), (4, 1)$ the weight of subset $ (1, 4), (2, 3), (3, 2)$ is $ \max\{1, 2, 3\} + \max\{4, 3, 2\} = 3 + 4 = 7$ .

The question is, having $ m \leq n$ , find the subset of size $ m$ (from given $ n$ rows) with maximal weight.

The problem looks trivial when $ m \geq k$ , but how can one solve it for $ m < k$ ? Looks like dynamic programming on subsets could work for small $ k$ , isn’t it? Are there other ways to do it?