Looks like a dynamic programming problem to me. Basically, you want to approach each division in sequence: maintain a set of the best available solutions for the divisions already considered, then add the remaining divisions one by one.
Specifically: you can combine two option matrices (as described for each division) into a combined option matrix. The rows and columns for this matrix are all possible sums of the rows and columns of the original matrices, and the payoff entries are the sum of the payoffs in the original matrices. Note that it is possible for rows and columns to overlap (if two sums end up being the same); in that case you clearly want to use the largest payoff. Also, you will need to store how each payoff was achieved, so you can eventually report how to achieve the optimum solution.
Note that, if the sizes of the original matrices are A and B, the size of resulting matrix could be O(A*B) in the worst case. However, you don't need to store any rows or columns that are larger than the total available resources. Also, as previously noted, rows and columns will be combined if there is more than one way to reach that sum. Finally, I believe you can drop any matrix entries whose payoffs are no better than other matrix entries that require less resources; the resulting sparse matrices may take much less space and computation to deal with.
In any case, once you've combined all your divisions into one final matrix, report the largest payoff entry as your solution.
