Minimum Traps with Deactivation Tool

A spy must traverse a grid from the start cell ((0,0)) to the destination cell ((n-1, m-1)). The grid is represented by an (n \times m) matrix where each cell is either 0 (safe cell) or 1 (trap). The spy can only move right or down at each step. In addition, he has a special tool that can be used at most once to deactivate (i.e. set to 0) all traps in a chosen row or a chosen column. This deactivation can be applied before the spy embarks on his journey.

The standard dynamic programming relation for computing the cost (number of traps encountered) without using the tool is given by:
[ \texttt{dp}[i][j] = \texttt{grid}[i][j] + \min(\texttt{dp}[i-1][j],,\texttt{dp}[i][j-1]) ]

Your task is to determine the minimum number of traps encountered on an optimal path, given that the spy may choose to use his deactivation tool on one row or one column.

inputFormat

Input is read from standard input. The first line contains two integers (n) and (m), representing the number of rows and columns of the grid respectively. This is followed by (n) lines, each containing (m) integers (0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer to standard output—the minimum number of traps encountered on the spy's path when the deactivation tool is used optimally.## sample

3 4
0 1 0 0
1 0 1 1
0 0 0 0

0