方取最小值(我自己取的奇葩名字)

题目背景

无

题目描述

在一个$n×n$的正方形方镇内，取一个长方形使得长方形之内所有数(包括边界)相加最小，求这个最小值。

输入格式

第一行输入$n$，意义如上述

第$2-n+1$行，每行$n$个数，表示这个$n×n$方镇

输出格式

最小值

样例

输入样例

3
-1 -1 9
-3 -2 -6
50 24 44

输出样例

-7

求比$O(n^4)$更快的做法