Паралельні процеси
Коли аналізуються паралельні процеси, які потребують синхронізації, часто важливо знати, які типи завдань можуть виконуватися одночасно. Розглянемо n завдань m типів. Два типи завдань називаються незалежними, якщо вони можуть виконуватися паралельно. Завдання одного типу завжди виконуються послідовно і не можуть бути незалежними.
Розглянемо послідовність завдань, що виконуються на k процесорах. Щосекунди можна виконати до k наступних завдань, якщо кожна пара з них може виконуватися паралельно. Зверніть увагу, що не можна пропускати завдання або відкладати їх на потім. Наприклад, якщо завдання типів A та B є незалежними, послідовність AABABBAB може бути виконана на двох процесорах за п'ять секунд. Один зі способів це зробити: (A−), (AB), (AB), (B−), (AB).
Інший спосіб виконати цю послідовність на двох процесорах: (A−), (AB), (AB), (BA), (B−). Ми кажемо, що два способи є суттєво різними, якщо існує така секунда, коли набори завдань, що виконуються, є різними. Можна побачити, що існує два суттєво різних способи виконати послідовність завдань AABABBAB на двох процесорах за мінімальний час. Якщо також враховувати, на якому процесорі виконується кожне завдання, існує 64 способи виконати даний набір завдань (у кожному з двох суттєво різних способів ми можемо обмінювати завдання між процесорами щосекунди). Тому ми кажемо, що існує 64 точних способи виконання набору завдань.
Знаючи типи завдань, які є незалежними, кількість процесорів та послідовність завдань, ви повинні визначити мінімальний час, необхідний для виконання завдань, кількість суттєво різних способів це зробити та кількість різних точних способів виконання.
Вхідні дані
Перша строка вхідного файлу містить n — кількість завдань (1 ≤ n ≤ 100), m — кількість типів завдань (1 ≤ m ≤ 26, типи завдань ідентифікуються першими m великими літерами англійського алфавіту), k — кількість процесорів (1 ≤ k ≤ 10) та p — кількість пар завдань, які є незалежними. Наступна строка містить p пар літер, що вказують на незалежні завдання. Остання строка містить n літер — послідовність завдань для виконання.
Вихідні дані
На першій строку вихідного файлу виведіть мінімальну кількість секунд, необхідну для виконання даних завдань. На другій строку виведіть кількість суттєво різних способів це зробити. На третій строку виведіть кількість точних способів.