Is this problem about picking optimal entries of a matrix NP-complete?
Reduce to maximum-weight bipartite matching.

If you just wanted ​ for each j, pick at most a($\hspace{.015 in}$j) entries from the j-th column ,

then the reduction would be

One of the parts is ​ ​ ​ one vertex for each row.

The other part is ​ ​ ​ for each j, a($\hspace{.015 in}$j) vertices for the j-th column .

The weight of each edge is the corresponding matrix entry.

and the reasoning would be

The ​ one vertex per row ​ ensures that at most one element will be picked for each row.

The ​ a($\hspace{.015 in}$j) vertices for the j-th column ​ allows the j-th column to be

used a($\hspace{.015 in}$j) times but prevents it from being used more than that.

The weights of the edges make the total weights of the matchings

correspond to your objective function.

.



For ​ for each j, pick exactly a($\hspace{.015 in}$j) entries from the j-th column , ​ you'd do:

Check whether-or-not ​ ​ ​ n ​ &lt; ​ a(1) + a(2) + a(3) + ... + a(m-1) + a(m) ​ .

If that inequality is true, then there are no feasible solutions.

Otherwise, construct the bipartite graph like above but letting the edge weights be

a(1) + a(2) + a(3) + ... + a(m-1) + a(m) + 1 ​ + ​ the corresponding matrix entry ​ .

This will make it so that all maximum-weight matchings use the whole column part,

thereby indicating exactly a($\hspace{.015 in}$j) entries for each j-th column.