Minimum Subrectangle Sum

You are given a two-dimensional grid of integers. Your task is to find the subrectangle (a contiguous block of rows and columns) whose sum is the smallest among all possible subrectangles in the grid. Note that the subrectangle can be as small as a single cell.

Note: Although the grid may typically contain non-negative numbers, negative integers may also appear, and they may lead to the minimum subrectangle sum.

The sum of a subrectangle defined by its top-left corner (i, j) and bottom-right corner (k, l) is the sum of all grid[x][y] with i ≤ x ≤ k and j ≤ y ≤ l. Your program should compute and output the smallest such sum.

The solution to this problem can be achieved using a two-dimensional extension of Kadane's algorithm.

inputFormat

The first line of input contains two space-separated integers n and m — the number of rows and columns of the grid.

Each of the following n lines contains m space-separated integers representing the grid.

Input is read from standard input (stdin).

outputFormat

Output a single integer — the smallest sum of any subrectangle within the grid. The output should be written to standard output (stdout).

3 3
1 2 3
4 -5 6
7 8 9

-5