Kruska

Ο Aladdin έχει βαρεθεί τη ζωή στο παλάτι. Έχει μια σταθερή δουλειά, τη σύζυγό του Jasmine, περιμένει παιδιά και η ζωή γίνεται μονότονη. Παρακινούμενος από όλα αυτά, αποφάσισε να ζήσει μια τελευταία περιπέτεια.
Αποφάσισε να βρει το Χρυσό Αχλάδι, ένα εξαιρετικά πολύτιμο θρυλικό αντικείμενο που κανείς δεν έχει καταφέρει να βρει.
Η έρημος που αναζητά ο Aladdin μπορεί να μοντελοποιηθεί ως ένα $N\times N$ πλέγμα κελιών. Οι γραμμές και οι στήλες είναι αριθμημένες από $1$ έως $N$ από πάνω προς τα κάτω και από αριστερά προς τα δεξιά. Μερικά από τα κελιά στην έρημο περιέχουν μάγους που βοηθούν την αναζήτηση του Aladdin με έναν ασυνήθιστο τρόπο.
Ο Aladdin ξεκινά την αναζήτησή του στην επάνω αριστερή γωνία της ερήμου μια Δευτέρα στραμμένος προς τα δεξιά. Η κίνησή του περιλαμβάνει την επανάληψη των εξης βημάτων:

1. Εάν το τρέχον κελί περιέχει έναν μάγο που είναι ξύπνιος, τότε ο Aladdin στρίβει $90$ μοίρες αριστερά ή δεξιά, ανάλογα με το τι λέει ο μάγος.
2. Αν η κίνηση προς τα εμπρός θα έβγαζε τον Aladdin από την έρημο, γυρίζει $180$ μοίρες.
3. Ο Aladdin προχωρά ένα κελί και του παίρνει ακριβώς μια μέρα.

Για κάθε μάγο γνωρίζουμε την τοποθεσία του και το πρόγραμμα δραστηριοτήτων του για κάθε μέρα της εβδομάδας. Το πρόγραμμα είναι μια συμβολοσειρά επτά ακριβώς γραμμάτων '$L$', '$R$' ή '$S$', και κάθε χαρακτήρας μας λέει τι κάνει ο μάγος μια μέρα της εβδομάδας (ξεκινώντας από τη Δευτέρα). Το γράμμα '$L$' σημαίνει ότι θα πει στον Aladdin να στρίψει αριστερά, '$R$' ότι θα πει στον Aladdin να στρίψει δεξιά, ενώ το '$S$' σημαίνει ότι ο μάγος κοιμάται εκείνη την ημέρα.
Μια παλιά προφητεία λέει ότι μετά από $K$ αλλαγές στην κατεύθυνση (στα βήματα 1 και/ή 2) ο Aladdin θα βρει το Αχλάδι. Γράψτε ένα πρόγραμμα που να υπολογίζει πόσες ημέρες θα διαρκέσει η αναζήτηση, σύμφωνα με την αρχαία προφητεία.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους $N$ και $K(2\le N\le 200,1\le K\le 1000000000)$, το μέγεθος της ερήμου και ο αριθμός των αλλαγών κατεύθυνσης στην προφητεία.
Η δεύτερη γραμμή περιέχει έναν ακέραιο $M(0\le M\le 10000)$, τον αριθμό των μάγων.
Κάθε μία από τις ακόλουθες $M$ γραμμές περιέχει δύο ακέραιους αριθμούς $R$ και $C(1\le R,C\le N)$ και μια συμβολοσειρά επτά γραμμάτων '$L$', '$R$' ή '$S$'. Οι αριθμοί αντιπροσωπεύουν τη γραμμή και τη στήλη όπου βρίσκεται ο μάγος, ενώ η συμβολοσειρά είναι το πρόγραμμά του.
Δεν υπάρχουν δύο μάγοι που θα μοιράζονται το ίδιο κελί, ούτε θα υπάρχει μάγος στο κελί $(1,1)$.

Έξοδος

Τυπώστε τη διάρκεια της αναζήτησης σε ημέρες.

Βαθμολογία

Στα αρχεία ελέγχου αξίας $50$ των πόντων, το $K$ θα είναι το πολύ $1000$.

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

input

3 1
0

output

2

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

Ο Aladdin κινείται δύο φορές, φτάνοντας στην άκρη της ερήμου. Στη συνέχεια γυρίζει 180 μοίρες και βρίσκει το Αχλάδι.

input

5 2
2
1 3 RRSRRRR
1 5 RRRRLRR

output

4

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

Ο Aladdin φτάνει στον πρώτο μάγο την τρίτη μέρα, αλλά ο μάγος κοιμάται έτσι ο Aladdin συνεχίζει στην ίδια κατεύθυνση. Μετά από άλλες δύο μέρες φτάνει στον άλλο μάγο που του λέει να στρίψει αριστερά. Ο Aladdin το κάνει, φτάνει στην άκρη της ερήμου, γυρίζει πίσω και βρίσκει το Αχλάδι.

input

5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS

output

10