Neo

Ας συμβολίσουμε το \(A_{i,j} ως το στοιχείο από τον πίνακα \)A\( που βρίσκεται στην \)i\(-οστή σειρά και την \)j\(-οστή στήλη. Λέμε ότι ο πίνακας \)Α~ είναι καλός αν ισχύει:

• ~r,\;s > 1~
• ~A_{1,1} + A_{r,s} \leq A_{1,s} + A_{r,1}~

όπου ~r~ υποδηλώνει τον αριθμό των γραμμών και ~s~ τον αριθμό των στηλών του πίνακα ~A~.

Επιπρόσθετα, λέμε ότι ένας πίνακας είναι εξαιρετικά κουλ εάν κάθε υποπίνακάς του με τουλάχιστον δύο σειρές και δύο στήλες είναι cool.

Είναι καθήκον σας να προσδιορίσετε τον μεγαλύτερο αριθμό στοιχείων που περιέχονται σε έναν εξαιρετικά κουλ υποπίνακα του δεδομένου πίνακα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους ~R,\;S\;(2 \leq R,\;S \leq 1\,000)~ που αντιπροσωπεύουν τις διαστάσεις του πίνακα.

Κάθε μία από τις ακόλουθες ~R~ γραμμές περιέχει ~S~ ακέραιους αριθμούς που αντιπροσωπεύουν τα στοιχεία του πίνακα. Τα στοιχεία του πίνακα θα είναι ακέραιοι από το διάστημα ~[-10^6,\;10^6]~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον μέγιστο αριθμό στοιχείων που περιέχονται σε έναν εξαιρετικά κουλ υποπίνακα του πίνακα από την είσοδο. Εάν δεν υπάρχει ένας εξαιρετικά κουλ υποπίνακας, τυπώστε 0.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας 60% των συνολικών πόντων, θα έχει επιπλέον ~R,\;S \leq 350~.

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

input

3 3
1 4 10
5 2 6
11 1 3

output

9

input

3 3
1 3 1
2 1 2
1 1 1

output

4

input

5 6
1 1 4 0 3 3
4 4 9 7 11 13
-3 -1 4 2 8 11
1 5 9 5 9 10
4 8 10 5 8 8

output

15

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

Η λύση είναι ένας πίνακας με πάνω αριστερή γωνία στο ~(3,\;2)~ και κάτω δεξιά γωνία στο ~(5,\;6~).