Dostava

Ο μικρός Ivica έπιασε πρόσφατα δουλειά παραδίδοντας πίτσες για την πιο δημοφιλή πιτσαρία της πόλης.
Στην αρχή της εργάσιμης ημέρας του, λαμβάνει μια λίστα με τις τοποθεσίες στις οποίες πρέπει να παραδώσει πίτσες, με τη σειρά με την οποία δίνονται οι τοποθεσίες.
Η πόλη χωρίζεται σε κελιά ~R \times C~. Οι σειρές αριθμούνται από ~1~ έως ~R~, στήλες ~1~ έως ~C~. Από κάθε κελί, είναι δυνατή η μετάβαση σε γειτονικά κελιά προς τα αριστερά και προς τα δεξιά. Η μετακίνηση προς τα πάνω ή προς τα κάτω επιτρέπεται μόνο στην πρώτη και την τελευταία στήλη (στήλες ~1~ και ~C~).
Η πιτσαρία βρίσκεται στην επάνω αριστερή γωνία ~(1, 1)~ και αυτή είναι η τοποθεσία από την οποία ξεκινά το Ivica. Ο Ivica παίρνει μαζί του όλες τις πίτσες που θα παραδώσει εκείνη την ημέρα, ώστε να μην χρειάζεται να επιστρέψει στην πιτσαρία μεταξύ των παραδόσεων ή μετά την τελευταία παράδοση.
Για κάθε τοποθεσία στην πόλη, ο Ivica ξέρει πόσο χρόνο θα αφιερώσει κάθε φορά που βρίσκεται σε αυτήν (προσπαθώντας να περάσει από τη διασταύρωση, για παράδειγμα).
Γράψτε ένα πρόγραμμα που να υπολογίζει τον μικρότερο χρόνο για να παραδώσει ο Ivica όλες τις πίτσες.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους αριθμούς ~R~ και ~C (1 \le R \le 2\,000,\; 1 \le C \le 200)~, τις διαστάσεις της πόλης.
Κάθε μία από τις ακόλουθες γραμμές ~R~ περιέχει ~C~ ακέραιους αριθμούς. Αυτοί είναι οι χρόνοι που περνάει ο Ivica κάθε φορά που μπαίνει μέσα μια τοποθεσία. Οι χρόνοι θα είναι ακέραιοι και θα ανήκουν στο κλειστό διάστημα ~[0,\; 5\,000]~.
Η επόμενη γραμμή περιέχει έναν ακέραιο αριθμό ~D (1 \le D \le 200\,000)~, τον αριθμό των παραδόσεων πίτσας εκείνη την ημέρα. (Όχι, δεν είναι καθόλου εξωπραγματικά μεγάλος αριθμός.)
Κάθε μία από τις ακόλουθες ~D~ γραμμές περιέχει δύο ακέραιους αριθμούς ~A~ και ~B (1 \le A \le R,\; 1 \le B \le C)~, τη θέση που πρέπει να παραδοθεί μια πίτσα. Οι πίτσες δίνονται με τη σειρά που πρέπει να παραδοθούν. Καμία τοποθεσία δεν θα δοθεί δύο φορές στη σειρά.

Έξοδος

Τυπώστε τον μικρότερο χρόνο που θα χρειαστεί ο Ivica για να παραδώσει όλες τις πίτσες.

Βαθμολογία

Στα αρχεία ελέγχου αξίας ~70~% των πόντων, το ~R~ θα είναι το πολύ ~250~.

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

input

3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2

output

17

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

Η συντομότερη διαδρομή διέρχεται από τις ακόλουθες τοποθεσίες:
~(1,\;1),\;(2,\;1),\;(3,\;1),\;(3,\;2),\;(3,\;3),\;(2,\;3),~ (1, 3)~,\;(2,\;3),~ (3 , 3)~,\;(2,\;3)~ και (2, 2).
Οι τοποθεσίες με έντονα γράμματα δείχνουν πού ο Mirko έκανε παραδόσεις.
Ο συνολικός χρόνος για τις παραδόσεις είναι ~1\,+\,2\,+\,1\,+\,0\,+\,1\,+\,2\,+\,2\,+\,2\,+\,1\,+\,2\,+\,3\,=\,17~.

input

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

output

9