Use dynamic programming.

Let dp[i][j] be the answer for the first i rows such that column j is chosen from row i.

Use the concept of cumulative array to optimize the complexity of the solution.