Kronican

Ο μικρός Mislav έχει ~N~ ποτήρια άπειρου όγκου και κάθε ποτήρι περιέχει λίγο νερό. Ο Mislav θέλει να πιει όλο το νερό, αλλά δεν θέλει να πιει από περισσότερα από ~K~ ποτήρια. Αυτό που μπορεί να κάνει ο Mislav με τα ποτήρια είναι να ρίχνει τον συνολικό όγκο νερού από το ένα ποτήρι στο άλλο.

Δυστυχώς, για τον Mislav έχει σημασία τι ποτήρι θα διαλέξει, γιατί δεν είναι όλα τα ποτήρια εξίσου μακριά από αυτόν. Πιο συγκεκριμένα, η ποσότητα της προσπάθειας που χρειάζεται για να χυθεί νερό από το ποτήρι με την ένδειξη ~i~ στο ποτήρι με την ένδειξη ~j~, συμβολίζεται με ~C_{ij}~.

Βοηθήστε τον Mislav και βρείτε τη σειρά ρίψης του νερού από το ένα ποτήρι στο άλλο έτσι ώστε το άθροισμα της προσπάθειας να είναι ελάχιστο.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιους αριθμούς ~N,\;K\;(1 \le K \le N \le 20)~.
Οι ακόλουθες ~N~ γραμμές περιέχουν ~N~ ακέραιους ~C_{ij}\;(0 \le C_{ij} \le 10^5)~. Η ~i~-οστή σειρά και η ~j~-οστή στήλη περιέχουν την τιμή ~C_{ij}~. Θα ισχύει ότι κάθε ~C_{ii}~ είναι ίσο με 0.

Έξοδος

Τυπώστε την ελάχιστη προσπάθεια που απαιτείται από τον Mislav για να πετύχει τον στόχο του.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας 40 βαθμών συνολικά, θα ισχύει ~N \le 10~.

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

input

33
011
101
110

output

0

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

Ο Mislav δεν χρειάζεται να ρίξει νερό για να πιει από το πολύ 3 ποτήρια.

input

32
011
101
110

output

1

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

Ο Mislav πρέπει να ρίξει το νερό ακριβώς από ένα (δεν έχει σημασία ποιο) ποτήρι σε οποιοδήποτε άλλο ποτήρι για να μείνουν μόνο δύο ποτήρια με νερό.

input

5 2
05432
70444
33012
43105
45550

output

5

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

Για να πετύχει ο Mislav την ελάχιστη λύση του 5, μπορεί να ρίξει νερό από το ποτήρι ~4~ στο ~3~ (προσπάθεια 1), μετά ~3 \rightarrow 5~ (προσπάθεια 2), και τέλος, ~1 \rightarrow 5~ (προσπάθεια 2). Συνολικά, ~1 + 2 + 2 = 5~ ποσότητα προσπάθειας.