# Find maximal subset with interesting weight function

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?

Definitely NP-hard, since it can be used to encode a maximisation form of Vertex Cover in which we ask for the maximum number of edges that can be covered by any subset of $$k$$ vertices: The input matrix here is just the incidence matrix of the graph, with vertices in the rows and edges in the columns.