Brick Breaker Maximum Score

Little Hong loves playing a game called Brick Breaker. At the beginning of the game, there is a grid of bricks with \(n\) rows and \(m\) columns. Little Hong starts with \(k\) bullets. Each time, she may use one bullet to shoot a column. When she shoots a column, the bottom-most remaining brick in that column is destroyed, and she earns the brick's score. Some bricks, when destroyed, give a bonus of one extra bullet. The game ends either when all bricks are destroyed or when there are no bullets left.

Before the game starts, Little Hong already knows the score and the bonus information for each brick. Note that the bricks in each column are arranged from the top row to the bottom row. However, the shooting order in a column is fixed: the bottom brick is destroyed first, then the brick just above it, and so on.

Your task is to help Little Hong determine the maximum possible score she can achieve if she plays optimally. Formally, for each column, if she decides to shoot \(x\) bricks (\(0 \le x \le n\)), then the bricks that will be destroyed are the bottom \(x\) bricks. Let the cumulative score from these bricks be \(S(x)\) and the number of bonus bullets obtained be \(B(x)\). Since every shot consumes one bullet and each bonus adds one bullet immediately after the shot, the net bullet cost for shooting \(x\) bricks in that column is \[ C(x) = x - B(x) \quad (0 \le C(x) \le x) . \] Little Hong can choose a nonnegative integer \(x_j\) for each column \(j\) such that the total net bullet cost \[ \sum_{j=1}^{m} \bigl(x_j - B_j(x_j)\bigr) \le k \] and the total score \[ \sum_{j=1}^{m} S_j(x_j) \] is maximized.

inputFormat

The input consists of the following:

1. The first line contains three integers \(n\), \(m\), and \(k\) \( (1 \le n, m \le 100,\ 1 \le k \le 10^4)\), representing the number of rows, the number of columns, and the initial number of bullets respectively.
2. The next \(n\) lines each contain \(m\) integers. These \(n\) lines represent the score matrix of the bricks. The \(i\)-th line corresponds to the \(i\)-th row (from top to bottom), and the \(j\)-th integer in a line is the score of the brick at row \(i\), column \(j\).
3. The next \(n\) lines each contain \(m\) integers (each either 0 or 1). This is the bonus matrix. In these \(n\) lines, the \(j\)-th integer in the \(i\)-th row indicates whether the brick at row \(i\), column \(j\) gives a bonus bullet (1 for bonus, 0 otherwise).

Note: In each column, the bricks are shot in order starting from the bottom row (i.e. row \(n\)) upward.

outputFormat

Output a single integer: the maximum score Little Hong can achieve by optimally choosing which bricks to shoot under the bullet constraint.

sample

2 1 1
5
10
0
0

10