Maximum Weight Subset

You are given a grid of dimensions n × m where each cell contains a positive integer representing the weight of a product. You need to choose a non-empty subset of these weights such that the total weight does not exceed a given limit W. Your task is to compute the maximum possible total weight that can be moved without exceeding W.

Mathematical Formulation:

Let \(\{a_{ij}\}\) for \(1 \leq i \leq n\) and \(1 \leq j \leq m\) be the weights, and let \(W\) be the maximum allowable sum. Find a subset \(S\) of these weights such that \(\sum_{(i,j)\in S} a_{ij} \leq W\) and \(\sum_{(i,j)\in S} a_{ij}\) is maximized.

inputFormat

The input is given via standard input and has the following format:

n m
row1 (m integers)
row2 (m integers)
...
rown (m integers)
W

Here, the first line contains two integers \(n\) and \(m\) separated by a space. The next \(n\) lines each contain \(m\) space-separated integers representing the grid. The last line contains the integer \(W\), the maximum allowed total weight.

outputFormat

Output, via standard output, a single integer: the maximum total weight of a chosen subset that does not exceed \(W\).

2 3
1 2 3
4 5 6
10

10