Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3755

Time Limit: 2 Seconds      Memory Limit: 65536 KB

As a small-game fan, Flandre loves playing the Mine-sweeping very much. He spends 23 hours playing the lowest level of Mine-sweeping every day.
One day, when Flandre is playing Mine-sweeping, a strange idea comes to him:
"Can I just calculate the minimum number of the mine in current state of the game ?"

To simplify this problem, we suppose the map is a N*(M*2+1) matrix and there are some mines in the grids of odd columns. You have got all the messages about the even columns which are represented as a N * M number matrix.
For example: N = 3, M = 2(# represent the mines, number means how many mines around it)
# 2 1 2 #
2 4 # 3 0
# 3 # 2 0
the messages about the even columns are:
2 2
4 3
3 2
Your task is to calculate the minimum number of mines with the messages matrix.


There are multiple test cases. For each test case:
The first line contains two integers N(1≤ N≤ 10), M(1≤ M≤ 10)
Then followed by N lines, each line contain M integers represent the messages matrix.
Process to the end of input.


For each the case, print the minimum number of mines.

Sample Input

3 2
2 2
4 3
3 2

Sample Output


Author: LUO, Jiewei
Source: ZOJ Monthly, January 2014
Submit    Status