Connecting Territories

Η Ava παίζει ένα παιχνίδι στρατηγικής σε ένα πλέγμα από πλακίδια. Κάθε πλακίδιο έχει ένα αντίστοιχο κόστος. Όταν τα κόστη των πλακιδίων διαβάζονται από αριστερά προς τα δεξιά, ξεκινώντας από την πρώτη γραμμή, εμφανίζεται ένα επαναλαμβανόμενο μοτίβο των πρώτων ~M~ θετικών ακεραίων σε αύξουσα σειρά: ~1~, ~2~, ~3~, ~...~, ~M~, ~1~, ~2~, ~3~, ~...~, ~M~, ~1~, ~2~, ~3~, ~...~. Σε αυτό το μοτίβο, το ~M~ αντιπροσωπεύει το μέγιστο κόστος ενός πλακιδίου. Στο πλέγμα πλακιδίων που παρουσιάζεται, το ~M~ είναι ίσο με ~5~.

Η Ava χρειάζεται να αγοράσει ένα πλακίδιο σε κάθε γραμμή, ώστε να δημιουργήσει μια διαδρομής διασύνδεσης από την πάνω περιοχή (πάνω από την πρώτη γραμμή των πλακιδίων) έως την κάτω περιοχή (κάτω από την τελευταία γραμμή των πλακιδίων). Το πρώτο πλακίδιο που αγοράζει πρέπει να βρίσκεται στην πρώτη γραμμή. Κάθε επόμενο πλακίδιο που αγοράζει πρέπει να έχει είτε κοινή πλευρά είτε κοινή γωνία με το πλακίδιο που αγόρασε προηγουμένως. Στο πλέγμα πλακιδίων που παρουσιάζεται παραπάνω, το κόστος της διαδρομής διασύνδεσης της Ava είναι ~9~.

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

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν θετικό ακέραιο ~R~, ο οποίος αντιπροσωπεύει τον αριθμό των γραμμών του πλέγματος. Η δεύτερη γραμμή θα περιέχει έναν θετικό ακέραιο ~C~, ο οποίος αντιπροσωπεύει τον αριθμό των στηλών του πλέγματος. Η τρίτη γραμμή θα περιέχει έναν θετικό ακέραιο ~M~, όπου ~M \le 100.000~, ο οποίος αντιπροσωπεύει το μέγιστο κόστος ενός πλακιδίου.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια	Περιορισμοί
~3~	~R = 2~ και ~C \le 10~	Υπάρχουν ~2~ γραμμές και το πολύ ~10~ στήλες.
~8~	~R \le 10~ και ~C \le 10~	Υπάρχουν το πολύ ~10~ γραμμές και το πολύ ~10~ στήλες.
~2~	~R \le 100~ και ~C \le 100~	Υπάρχουν το πολύ ~100~ γραμμές και το πολύ ~100~ στήλες.
~2~	~R \le 20.000~ και ~C \le 20.000~	Το πλέγμα μπορεί να είναι πολύ μεγάλο.

Έξοδος

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

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

input

3
5
7

output

6

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

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