Domino

Ο Mirko έλαβε έναν πίνακα ~N \times N~ για τα γενέθλιά του, όπου ένας μη αρνητικός ακέραιος είναι γραμμένος σε κάθε πεδίο του πίνακα. Δυστυχώς, οι γραμμένοι αριθμοί είναι πολύ μεγάλοι για το γούστο του Mirko, οπότε θα τοποθετήσει K ντόμινο πάνω από το τραπέζι που θα καλύψει τα πεδία που είναι πολύ μεγάλα.
Πιο συγκεκριμένα, ο Mirko τοποθετεί τα ντόμινο σύμφωνα με τους ακόλουθους κανόνες:

• κάθε ντόμινο καλύπτει δύο πεδία του πίνακα που βρίσκονται δίπλα σε μια σειρά ή σε μια στήλη,
• τα ντόμινο δεν επικαλύπτονται (αλλά μπορούν να αγγίξουν),
• το άθροισμα όλων των ορατών (ακάλυπτων) πεδίων πρέπει να είναι όσο το δυνατόν μικρότερο.

Είναι καθήκον σας να προσδιορίσετε το απαιτούμενο ελάχιστο άθροισμα ορατών πεδίων. Τα δεδομένα της δοκιμής θα είναι τέτοια που θα είναι πάντα δυνατή η τοποθέτηση ~K~ ντόμινο χωρίς επικάλυψη..

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N\;(1 \leq N \leq 2000)~, τις διαστάσεις του πίνακα και ~K\;(1 \leq K \leq 8)~, τον αριθμό των ντόμινο. Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ~N~ ακέραιους αριθμούς από το διάστημα [0, 1000]. Αυτοί οι ~N \times N~ αριθμοί περιγράφουν τον πίνακα του Mirko.

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 70 πόντων, θα κρατήσει ~K \leq 5~.

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

input

3 1
2 7 6
9 5 1
4 3 8

output

31

input

4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1

output

17