Triangle: The Data Structure

Σε ένα παράλληλο σύμπαν, η πιο σημαντική δομή δεδομένων στην επιστήμη των υπολογιστών είναι το τρίγωνο. Ένα τρίγωνο μεγέθους ~M~ αποτελείται από ~M~ σειρές, με την ~i~-οστή σειρά να περιέχει ~i~ στοιχεία. Επιπλέον, αυτές οι σειρές πρέπει να είναι διατεταγμένες έτσι ώστε να έχουν τη μορφή ενός ισόπλευρου τριγώνου. Δηλαδή, κάθε σειρά είναι κεντραρισμένη γύρω από μια κατακόρυφη γραμμή συμμετρίας που διέρχεται από το κέντρο του τριγώνου. Για παράδειγμα, το διάγραμμα παρακάτω δείχνει ένα τρίγωνο μεγέθους ~4~:

Ένα τρίγωνο περιέχει υπο-τρίγωνα. Για παράδειγμα, το παραπάνω τρίγωνο περιέχει δέκα υποτρίγωνα μεγέθους ~1~, έξι υποτρίγωνα μεγέθους ~2~ (δύο από τα οποία είναι το τρίγωνο που περιέχει τα ~(3, 1, 2)~ και το τρίγωνο που περιέχει τα ~(4, 6, 1)~), τρία υποτρίγωνα μεγέθους ~3~ (ένα από τα οποία περιέχει τα ~(2, 2, 1, 1, 4, 2)~). Σημειώστε ότι κάθε τρίγωνο είναι υπο-τρίγωνο του εαυτού του.

Σας δίνεται ένα τρίγωνο μεγέθους ~N~ και πρέπει να βρείτε το άθροισμα των μέγιστων στοιχείων κάθε υπο-τριγώνου μεγέθους ~K~.

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο ακέραιους αριθμούς ~N~ και ~K\;(1 \le K \le N \le 3000)~.

Θα ακολουθούν ~N~ γραμμές που περιγράφουν το τρίγωνο. Η ~i~-οστή από αυτές τις γραμμές θα περιέχει ~i~ ακέραιους αριθμούς χωρισμένους με κενά διαστήματα ~a_{i,j}\;(0 \le a_{i,j} \le 10^{9})~ χωρισμένους με κενά διαστήματα, που αντιπροσωπεύουν την ~i~-οστή σειρά του τριγώνου.

Για ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 1000~.

Έξοδος

Εξάγετε το ακέραιο άθροισμα των μέγιστων στοιχείων κάθε υποτριγώνου μεγέθους ~K~.

Παράδειγμα

input

4 2
3
1 2
4 2 1
6 1 4 2

output

23