Early Exam Evacuation

Βρίσκετε τον εαυτό σας να γράφει μια εξέταση σε ένα μακρύ, στενό αμφιθέατρο - έχει ~N~ (~1 \le N \le 10^5~) σειρές, αριθμημένες από το ~1 ... N~ από μπροστά προς τα πίσω, καθεμία από τις οποίες έχει ~6~ καθίσματα, ~3~ σε κάθε πλευρά του διαδρόμου που περνά από τη μέση του αμφιθεάτρου. Κάθε κάθισμα αναγνωρίζεται αμέσως από τον αριθμό της σειράς του ακολουθούμενο από ένα γράμμα από το "A" στο "F", το οποίο υποδεικνύει τη θέση του σε αυτή τη σειρά (με το κάθισμα "A" στο άκρο αριστερά, και "F" στο άκρο δεξιά). Ο διάδρομος βρίσκεται ανάμεσα στα καθίσματα "C" και "D" σε κάθε σειρά. Το αμφιθέατρο διαθέτει επίσης δύο ασφαλή δωμάτια - ένα μπροστά (μπροστά από τη σειρά ~1~), και ένα στο πίσω μέρος (πίσω από τη σειρά ~N~).

Κάθε κάθισμα στο αμφιθέατρο αρχικά καταλαμβάνεται από ακριβώς έναν εξεταζόμενο ανά θέση. Ωστόσο, κατά τη διάρκεια της εξέτασης, οι διαφορετικοί εξεταζόμενοι αποφασίζουν ότι έχουν γράψει ό, τι μπορούν στην εξέταση, και στη συνέχεια θα ήθελαν να εγκαταλείψουν το αμφιθέατρο, ο ένας μετά τον άλλον. Ο ~i~-οστος εξεταζόμενος είναι στο κάθισμα ~R_i C_i~ (~1 \le R_i \le N, C_i~ είναι ένα από τα "Α" .. "F"). Όταν ο εξεταζόμενος εγκαταλείπει το αμφιθέατρο, πρέπει να μείνουν σε ένα από τα ασφαλή δωμάτια μέχρι το τέλος της εξέτασης. Ευτυχώς, και τα δύο ασφαλή δωμάτια μπορούν να κρατήσουν όσους ανθρώπους είναι απαραίτητο.

Οι εξεταζόμενοι όχι μόνο ανησυχούν για τις εξετάσεις, αλλά θα ήθελαν τη ζωή τους να είναι όσο το δυνατόν πιο βολική γίνεται - οπότε, τους ενδιαφέρει να συνεργαστούν για να ελαχιστοποιηθεί η συνολική ταλαιπωρία που βιώνουν όλοι τους. Η ταλαιπωρία που βιώνει ένας εξεταζόμενος είναι ~A_x + B_y~, Όπου οι ~A~ και ~B~ είναι δεδομένες σταθερές (~0 \le A, B \le 10^9~), το ~x~ είναι ο αριθμός διαφορετικών ανθρώπων που περάσαν στο δρόμο προς το επιλεγμένο ασφαλές δωμάτιο (εξηγείται παρακάτω), και το ~y~ είναι ο αριθμός των ατόμων που βρίσκονται ήδη στο ασφαλές δωμάτιο πριν εισέλθει εκείνος ο εξεταζόμενος. Σημειώστε ότι εάν ένας εξεταζόμενος δεν φύγει από το κάθισμά του, η ταλαιπωρία του είναι ~0~.

Όταν κάποιος περπατάει από ένα κάθισμα σε ένα ασφαλές δωμάτιο, πρέπει πρώτα να περάσει οποιονδήποτε άλλο εξεταζόμενο στην ίδια σειρά στο δρόμο προς το διάδρομο, και στη συνέχεια κάθε εξεταζόμενο στα καθίσματα δίπλα στο διάδρομο από αυτή τη σειρά σε σειρά ~1~ ή ~N~ (ανάλογα με το ποιο ασφαλές δωμάτιο επιλέγεται). Σημειώστε ότι κάθε κενό κάθισμα που περνάτε στο δρόμο σας δεν μετρά σε αυτή την αξία.

Μπορείτε να βοηθήσετε τους καημένους εξεταζόμενους να κάνουν τη ζωή τους όσο το δυνατόν πιο βολική;

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις, χωρισμένους με κενό, ακέραιους: ~N~ (~1 \le N \le 10^5~), τον αριθμό των σειρών στο αμφιθέατρο, ~M~ (~1 \le M \le 6N~), τον αριθμό των εξεταζόμενων που φεύγουν νωρίς, ~A~ ακολουθούμενο από το ~B~ (~1 \le A, B \le 10^9~), τις σταθερές που χρησιμοποιούνται για να καθοριστεί η ταλαιπωρία που θα προκληθεί από ένα εξεταζόμενο που φεύγει νωρίς.

Οι επόμενες ~M~ γραμμές καθεμία περιέχουν έναν ακέραιο ακολουθούμενο από ένα χαρακτήρα, ~R_i~ και ~C_i~, για ~i = 1 ... N~ με τη σειρά, όπου ~1 \le R_i \le N~ και ~C_i \in ~ "A" ... "F".

Βαθμολογία

Μπορείτε να υποθέσετε ότι για τις περιπτώσεις δοκιμής αξίας 60% των βαθμών, ~M \le 5\,000~.

Έξοδος

Εκτυπώστε τον ακέραιο ο οποίος είναι η ελάχιστη συνολική ταλαιπωρία που βίωσαν από όλους τους ~M~ εξεταζόμενους που φεύγουν νωρίς.

Παράδειγμα

input

5 5 3 4
3E
1D
5C
1E
4A

output

55

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

Μία βέλτιστη στρατηγική έχει ως εξής. Το πρώτο άτομο που φεύγει μπορεί να πάει στο μπροστά ασφαλές δωμάτιο, περνώντας έξι άτομα στο δρόμο του (στις θέσεις 3D, 3C, 2D, 2C, 1D και 1C) για μία ταλαιπωρία της τάξης του ~3 \cdot 6 + 4 \cdot 0 = 18~. Το δεύτερο άτομο που φεύγει μπορεί επίσης να πάει στο μπροστά ασφαλές δωμάτιο περνώντας μόνο ένα άτομο (στη θέση 1C) και βρίσκοντας ένα άτομο στο ασφαλές δωμάτιο, για μία ταλαιπωρία της τάξης του ~3 \cdot 1 + 4 \cdot 1 = 7~. Το τρίτο άτομο μπορεί να πάει στο πίσω ασφαλές δωμάτιο, περνώντας ένα άτομο για μία ταλαιπωρία ~3~. Το τέταρτο άτομο μπορεί να ακολουθήσει τους πρώτους δύο στο μπροστά ασφαλές δωμάτιο, περνώντας μόνο ένα άτομο (καθώς η θέση 1D είναι κενή σε εκέινο το σημείο) για μία ταλαιπωρία ~11~. Τέλος, το πέμπτο άτομο που φεύγει μπορεί να πάει στο πίσω ασφαλές δωμάτιο, περνώντας τέσσερα άτομα και συναντώντας ένα άτομο στο πίσω ασφαλές δωμάτιο για μια ταλαιπωρία ~16~. Η συνολική ταλαιπωρία που βίωσαν οι εξεταζόμενοι με αυτή τη στρατηγική είναι ~18 + 7 + 3 + 11 + 16 = 55~.