[Hidden]
#### 1336. F. Sub Matrix Sum

#### Description

You have written many programs to search mazes so matrix search shouldn’t be any different, or will it?

The Problem:

An integer matrix with R rows and C columns has sub matrices. We want to select a sub matrix with sum (the sum of all integers in it) greater than or equal to a given integer S. We want the size of the sub matrix to be the least possible. The size of a sub matrix is defined as the number of elements in that sub matrix (i.e., number of rows * number of columns in that sub matrix).

#### Input

The first input line consists of three integers R, C (1 ≤ R ≤ 100,000; 1 ≤ C ≤ 100,000; 1 ≤ R*C ≤ 100,000) and S. Next R lines contain the description of the matrix. Each of these R lines contains C integers separated by a single space. All integers (other than R and C) are between -10^{9} and +10^{9}, inclusive.
#### Output

Print the size of the minimum sub matrix whose sum is greater or equal to the given S. If there is no such sub matrix, output -1.
#### Samples

#### Source

UCF2019 PRACTICE

The Problem:

An integer matrix with R rows and C columns has sub matrices. We want to select a sub matrix with sum (the sum of all integers in it) greater than or equal to a given integer S. We want the size of the sub matrix to be the least possible. The size of a sub matrix is defined as the number of elements in that sub matrix (i.e., number of rows * number of columns in that sub matrix).

Time Limit: | 2000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 7 / 39 |

Tags: |