Domine

Ο Mirko έχει μια σκακιέρα με ~N~ σειρές και μόλις τρεις στήλες. Η Slavica έχει γράψει έναν ακέραιο σε κάθε πεδίο. Ο Mirko έχει ~K~ ντόμινο στη διάθεσή του, με τις διαστάσεις τους να είναι ~2 \times 1~, και πρέπει να τα τακτοποιήσει όλα στον πίνακα χωρίς να επικαλύπτονται, με τρόπο ώστε κάθε ντόμινο να καλύπτει ακριβώς δύο πεδία του ταμπλό. Μπορεί να περιστρέψει τα ντόμινο όπως θέλει.

Βοηθήστε τον Mirko να καλύψει το μεγαλύτερο δυνατό άθροισμα αριθμών με το ντόμινο!

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 1000)~, τον αριθμό των σειρών και ~K\;(1 \leq K \leq 1000)~, τον αριθμό των διαθέσιμων ντόμινο.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει τρεις ακέραιους αριθμούς γραμμένους στην ~i~-οστή σειρά του πίνακα. Όλοι οι αριθμοί θα είναι μικρότεροι από το ~10^6~ κατά απόλυτη τιμή.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το μέγιστο δυνατό άθροισμα για κάλυψη με ακριβώς ~K~ ντόμινο.

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

input

5 3
2 1 -1
1 3 2
0 2 3
2 1 1
3 3 0

output

16

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

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

input

2 2
0 4 1
3 5 1

output

13