Collecting Treasures on a Grid

ZJY is studying combinatorial mathematics by working on a challenging problem. You are given a grid with n rows and m columns. Each cell in the grid contains a certain number of treasures. In one walk, you start from the top‐left cell and move only right or down until you reach the bottom-right cell. When you pass through a cell, you can collect at most one treasure from that cell.

Your task is to determine the minimum number of walks required so that it is possible to collect all the treasures in the grid.

Key Observation: For any set of walks, note that each walk (being a monotonic path) can visit at most one cell from any antichain (a set of cells no one of which is reachable from any other, in terms of grid order). In a grid where you can only move right or down, all cells with the same sum of coordinates (i.e. all cells on the same anti‐diagonal) form an antichain. Thus, if we denote the number of treasures in cell \( (i,j) \) as \( a_{ij} \), then each walk can contribute at most 1 to the collection of treasures from any given anti‐diagonal. Consequently, the minimum number of walks needed is \[ W = \max_{d=0}^{n+m-2} \Bigl\{\sum_{i+j=d} a_{ij}\Bigr\}. \]

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns in the grid, respectively. Each of the next n lines contains m non-negative integers. The j-th integer in the i-th line denotes the number of treasures in cell \( (i, j) \).

outputFormat

Output a single integer — the minimum number of walks required to collect all the treasures, under the constraint that during one walk at most one treasure can be collected from each visited cell.

sample

2 2
1 2
3 4

5