Maximizing Matrix Path Score

You are given an n × m matrix consisting only of the characters \(0\), \(1\) and \(?\). The rows are numbered from \(1\) to \(n\) (top to bottom) and the columns are numbered from \(1\) to \(m\) (left to right). Initially, you are at the top‐left cell \((1,1)\) and you want to reach the bottom‐right cell \((n,m)\). You can only move either right or down at each step. Along your path (including the starting and ending cells), each time you pass a cell containing the character \(1\) you gain one point; passing a cell with any other character does not add any points.

You are allowed to change at most \(x\) occurrences of the character \(?\) in the matrix to \(1\) before you start moving. After making these modifications, you will choose a path from \((1,1)\) to \((n,m)\) in such a way that your score is maximized. Your task is to compute the maximum score you can achieve.

Note:

• If a cell originally contains \(?\) and you change it to \(1\), it will count as \(1\) when you pass through it.
• You are not allowed to change any cell that contains \(0\) or \(1\).
• The path is a sequence of moves that only goes right or down.

inputFormat

The first line of input contains three integers \(n\), \(m\) and \(x\) where \(1 \leq n, m \leq 1000\) (the constraints may vary) and \(0 \leq x \leq \) (the number of \(?) characters in the matrix).

The following \(n\) lines each contain a string of length \(m\), representing the rows of the matrix. Each character of the string is either \(0\), \(1\) or \(?\).

outputFormat

Output a single integer — the maximum score that can be achieved under the given conditions.

sample

2 2 1
1?
?1

3