Ratar

Μετά την αποτυχημένη θητεία του Mirko ως προπονητής και μια παροδική εμμονή με κροατικές λιχουδιές με κρέας, τα προβλήματα βάρους του τον έχουν παρακινήσει να εργαστεί σκληρά ως αγρότης. Έχει μετακομίσει σε ένα χωριό όπου μένει ο φίλος του Slavko. Οι αγρότες στο χωριό μοιράζονται ένα μεγάλο κοινό οικόπεδο σε σχήμα τετραγώνου ~N \times N~, χωρισμένο σε ~N^2~ μοναδιαία τετράγωνα. Ένα μοναδιαίο τετράγωνο στις συντεταγμένες² ~(i,\;j)~ φέρνει το εισόδημα ~A_{ij}~, το οποίο μπορεί να είναι αρνητικό (για παράδειγμα, εάν το τετράγωνο πρέπει να διατηρηθεί αλλά δεν καλλιεργείται). Οι αγρότες χωρίζουν πάντα την κοινή γη σε μικρότερα ορθογώνια χωράφια με άκρες παράλληλες με τις άκρες της κοινής γης.

Ο Slavko είναι δύσπιστος για τον Mirko από την αποτυχία του ως προπονητής, γι' αυτό επιμένει να τους εκχωρηθεί γη με το ίδιο συνολικό εισόδημα, αλλά και ότι τα δύο οικόπεδα μοιράζονται ακριβώς μια κοινή γωνία, ώστε οι δύο φίλοι να μπορούν να παρακολουθούν ο ένας τον άλλον (ο Σλάβκο ξέρει ότι ο Μίρκο είναι επιρρεπής στις κακοτοπιές). Η κοινή γωνία πρέπει να είναι το μόνο σημείο όπου συναντώνται τα δύο οικόπεδα, προκειμένου να αποφευχθούν επιχειρήματα που σχετίζονται με τα σύνορα.

Σας δίνεται περιγραφή του κοινόχρηστου οικοπέδου. Βρείτε τον συνολικό αριθμό των ζευγών οικοπέδων που ικανοποιούν τα κριτήρια του Slavko.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N (1 \le N \le 50)~, τις διαστάσεις του κοινόχρηστου οικοπέδου.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ~N~ αριθμούς χωρισμένους σε διάστημα ~A_{ij}\;(-1000 < A_{ij} < 1000)~, το εισόδημα που παρέχεται από το αντίστοιχο οικόπεδο.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον συνολικό αριθμό των ζευγών γραφικών που ικανοποιούν τη δεδομένη συνθήκη.

Βαθμολογία

Σε δεδομένα δοκιμής αξίας τουλάχιστον ~40~% των συνολικών πόντων, το ~N~ θα είναι το πολύ 10.

Παραδείγματα

input

3
1 2 3
2 3 4
3 4 8

output

7

Επεξήγηση του 1ου παραδείγματος:

Τα πιθανά ζεύγη ορθογωνίων είναι:
~(0,\;0)-(1,\;1)~ και ~(2,\;2)-(2,\;2),\;(1,\;0)-(1,\;0)~ και ~(0,\;1)-(0,\;1),\;(2,\;0)-(2,\;0)~ και ~(1,\;1)-(1,\;1),\;(1,\;1)-(1,\;1)~ και ~(0,\;2)-(0,\;2),\;(2,\;1)-(2,\;1)~ και ~(1,\;2)-(1,\;2),\;(2,\;0)-(2,\;1)~ και ~(0,\;2)-(1,\;2),\;(1,\;0)-(2,\;0)~ και ~(0,\;1)-(0,\;2)~.

input

4
-1 -1 -1 -1
1 2 3 4
1 2 3 4
1 2 3 4

output

10

input

5
-1 -1 -1 -1 -1
-2 -2 -2 -2 -2
-3 -3 -3 -3 -3
-4 -4 -4 -4 -4
-5 -5 -5 -5 -5

output

36

²Ο πρώτος αριθμός στην παρένθεση υποδηλώνει τη γραμμή και ο δεύτερος αριθμός τη στήλη.