Fixing Disks

Παίζετε ένα παιχνίδι με μια στοίβα ~N~ δίσκων (~1 \le N \le 100~). Ο στόχος του παιχνιδιού είναι να αφαιρέσετε όλους τους δίσκους από τη στοίβα σας. Ωστόσο, υπάρχει ένα κόστος που σχετίζεται με την αφαίρεση δίσκων και εσείς επιθυμείτε να ελαχιστοποιήσετε το κόστος αφαίρεσης όλων των δίσκων από τη στοίβα σας.

Κάθε δίσκος περιέχει μια ετικέτα, με την ετικέτα ~L~ να ανήκει στο διάστημα ~1 \le L \le 20~.

Σας δίνεται επίσης μια "Κύρια στοίβα" από ~N~ δίσκους που μπορείτε να χρησιμοποιήσετε για να σας βοηθήσει να αφαιρέσετε δίσκους από τη στοίβα σας.

Μπορείτε να αφαιρέσετε δίσκους από την κορυφή της στοίβας δίσκων σας με δύο τρόπους:

1. αφαιρέστε έναν δίσκο στην κορυφή της στοίβας σας: εάν η ετικέτα του δίσκου στην κορυφή της στοίβας σας είναι ~c~, αυτός ο δίσκος μπορεί να αφαιρεθεί από τη στοίβα σας με κόστος ~c~.

2. αφαιρέστε έναν δίσκο τόσο από την κορυφή της Κύριας στοίβας όσο και από την κορυφή της στοίβας σας, εάν η ετικέτα είναι ίδια μεταξύ των δύο δίσκων: σε αυτήν την περίπτωση, δεν υπάρχει κόστος με την αφαίρεση και των δύο δίσκων.

Επιτρέπεται επίσης να τροποποιήσετε τη σειρά των κορυφαίων ~K~ (~1 \le K \le 4~) στοιχείων της στοίβας σας, αρκεί αμέσως μετά από κάθε τροποποίηση, να αφαιρείτε το επάνω στοιχείο της στοίβας σας. Υπάρχουν τρεις επιτρεπόμενες τροποποιήσεις:

1. Αντιστροφή: μπορείτε να αντιστρέψετε τη σειρά των κορυφαίων ~r~ (~2 \le r \le K~) δίσκων στη στοίβα σας. Με άλλα λόγια, εάν οι κορυφαίοι ~r~ δίσκοι είναι ~d_1, d_2, ..., d_r~ (διαβάζοντας από πάνω προς τα κάτω), τότε μετά από αυτή την πράξη, οι κορυφαίοι ~r~ δίσκοι θα είναι ~d_r, ..., d_2, d_1~ (διαβάζοντας από πάνω προς τα κάτω). Το κόστος της μίας πράξης αντιστροφής είναι ~R~ (~1 \le R \le 1\,000\,000~).

2. (Κυκλική μετατόπιση) Επάνω: μπορείτε να μετατοπίσετε έναν δίσκο προς τα πάνω στην περιοχή των επάνω ~u~ δίσκων (~2 \le u \le K~). Για για παράδειγμα, εάν οι τέσσερις πρώτοι δίσκοι είναι ~d_1, d_2, d_3, d_4~ (διαβάζοντας από πάνω προς τα κάτω), μπορείτε να εκτελέσετε μετατόπιση προς τα πάνω στο εύρος των τριών κορυφαίων στοιχείων για να λάβετε ~d_2, d_3, d_1, d_4~ ή μια μετατόπιση προς τα πάνω των τεσσάρων κορυφαίων στοιχείων για να πάρουμε ~d_2, d_3, d_4, d_1~. Το κόστος μίας μετατόπισης προς τα επάνω είναι ~U~ (~1 \le U \le 1\,000\,000~).

3. (Κυκλική μετατόπιση) Κάτω: μπορείτε να μετακινήσετε προς τα κάτω έναν δίσκο στο εύρος των επάνω ~d~ δίσκων (~2 \le d \le K~). Για παράδειγμα, εάν οι τέσσερις πρώτοι δίσκοι είναι ~d_1, d_2, d_3, d_4~ (διαβάζοντας από πάνω προς τα κάτω), μπορείτε να πραγματοποιήσετε μια μετατόπιση προς τα κάτω στο εύρος των τριών κορυφαίων στοιχείων για να λάβετε ~d_3, d_1, d_2, d_4~ ή μία μετατόπιση προς τα κάτω των τεσσάρων κορυφαίων στοιχείων για να πάρετε ~d_4, d_1, d_2, d_3~. Το κόστος μιας μετατόπισης προς τα κάτω είναι ~D~ (~1 \le D \le 1\,000\,000~).

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

Υπάρχει ένας επιπλέον περιορισμός. Σε οποιοδήποτε σημείο του παιχνιδιού, αν αφαιρείται ένας δίσκος στο επίπεδο ~j~ (τα επίπεδα ξεκινούν από το ~0~ στο κάτω μέρος της στοίβας), μετά όλα τα στοιχεία που ήταν αρχικά στο επίπεδο ~j + M~ ή υψηλότερο πρέπει να έχει ήδη αφαιρεθεί, όπου ~1 \le M \le 5~.

Ελαχιστοποιήστε το κόστος που απαιτείται για να αφαιρέσετε όλα τα στοιχεία από τη στοίβα σας.

Είσοδος

Η πρώτη γραμμή θα περιέχει ~6~, χωρισμένους με κενό, ακέραιους: ~N, K, M, D, U, R~ όπου:

• ~N~ είναι ο αριθμός των δίσκων σε κάθε μία από τις στοίβες (~1 \le N \le 100~)

• ~K~, το μέγιστο βάθος στο οποίο μπορούν να γίνουν πράξεις (~1 \le K 4~)

• ~M~, το όριο πριν από το οποίο μπορούν να αφαιρεθούν στοιχεία από τη στοίβα μας, (~1 \le M \le 5~)

• ~D~, το κόστος για μία μετατόπιση στην οποία το τελευταίο στοιχείο του επιλεγμένου διαστήματος πηγαίνει στην κορυφή (~1 \le D \le 10^6~)

• ~U~, το κόστος για μία πράξη μετατόπισης προς τα πάνω (στην οποία το κορυφαίο στοιχείο του επιλεγμένου διαστήματος πηγαίνει στον πάτο), (~1 \le U \le 10^6~)

• ~R~, το κόστος για να αντιστρέψουμε τα κορυφαία στοιχεία του επιλεγμένου διαστήματος (~1 \le R \le 10^6~)

Ακολουθούν ~2N~ γραμμές, με καθεμία να περιέχει έναν αριθμό ~L~ (~1 \le L \le 20~). Οι πρώτες ~N~ γραμμές θα περιέχουν τις ετικέτες των δίσκων της Κύριας στοίβας, από πάνω προς τα κάτω. Οι επόμενες ~N~ γραμμές θα περιέχουν τις ετικέτες των δίσκων στην στοίβα σας, από πάνω προς τα κάτω.

Σημείωση: για το ~20~% των βαθμών για αυτό το ερώτημα, μπορείτε να υποθέσετε ότι ~K \le 2~.

Έξοδος

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

Παράδειγμα

input

7 3 3 4 4 3
5
6
3
5
4
1
2
3
5
6
5
1
4
1

output

5

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

Πηγαίνουμε το ~3~ στον πάτο και μετατοπίζουμε τους δύο δίσκους απο κάτω του προς τα πάνω, με κόστος ~4~. Έπειτα αφαιρούμε τέσσερις δίσκους από κάθε στοίβα, αφαιρούμε ένα ~1~ από την στοίβα μας, με κόστος ~1~ και αφαιρούμε δύο δίσκους από κάθε στοίβα.