Matrix of given integers


a1,1 a1,2 ... a1, n
a2,1 a2,2 ... a2, n
::
an, 1 an, 2 ... an, n


Then, create a program that outputs the maximum value of the sum of one or more consecutive terms (submatrix) in the vertical and horizontal directions and ends.



Input

The input data is given in the following format.


n
a1,1 a1,2 ... a1, n
a2,1 a2,2 ... a2, n
::
an, 1 an, 2 ... an, n


n is 1 or more and 100 or less, and ai, j is -10000 or more and 10000 or less.

Output

Print the maximum value on one line.

Examples

Input

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


Output

16


Input

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


Output

15

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int[][] list = new int[n][n];
		int[][] su   = new int[n][n+1];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				list[i][j] = sc.nextInt();

			}
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				su[i][j+1] = list[i][j];
				if(j != 0) {
					su[i][j+1] += su[i][j];
				}
			}
		}

		long max = Long.MIN_VALUE;
		for(int i = 0; i < n+1; i++) {
			for(int j = i+1; j < n+1; j++) {
				
				for(int k = 0; k < n; k++) {
					int sum = 0;
					for(int l = k; l < n; l++) {
					sum += su[l][j] - su[l][i];
					if(sum > max) max = sum;
					}
				}
			}
		}
		out.println(max);
		out.flush();
	}
}
		
//------------------------------//
//-----------//
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
    
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
    

}