Параллельные процессы
При анализе параллельных процессов, требующих синхронизации, важно понимать, какие типы задач могут выполняться одновременно. Рассмотрим 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 букв — последовательность задач для выполнения.
Выходные данные
На первой строке выходного файла выведите минимальное количество секунд, необходимое для выполнения данных задач. На второй строке выведите количество существенно различных способов выполнения. На третьей строке выведите количество точных способов выполнения.