eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Parallel Processes

Parallel Processes

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

When analyzing parallel processes that need synchronization, it is often important to know which types of tasks can be executed in parallel. Consider n tasks of m types. Let us call two types of tasks independent, if they can be executed in parallel. Tasks of one type are never independent and must be run sequentially.

Consider a sequence of tasks to be executed on k processors. Each second up to k next tasks can be executed if each pair of them can be run in parallel. Note, that it is not allowed to skip tasks or to save tasks for future execution. For example, if tasks of types A and B are independent, the sequence AABABBAB can be executed on two processors in five seconds, one way to do so is (A−), (AB), (AB), (B−), (AB).

The other way to run the given sequence of tasks on two processors is (A−), (AB), (AB), (BA), (B−). We say that two ways are essentially different if there is some second when the sets of tasks that are being executed are different. One can see that there are two essentially different ways to run the sequence AABABBAB of tasks on two processors in minimal time. If we also take into account which processor each task is executed on, there are 64 ways to execute the given set of tasks (in each of the two essentially different ways we can exchange the tasks between processors each second). So we say that there are 64exact ways to execute the set of tasks.

Given types of tasks that are independent, the number of processors, and the sequence of tasks, you have to find out the minimal time required to execute the tasks, the number of essentially different ways to do so, and the number of different exact ways of the execution.

Входные данные

The first line of the input file contains n — the number of tasks (1n100), m — the number of types of tasks (1m26, types of tasks are identified with first m capital letters of English alphabet), k — the number of processors (1k10) and p — the number of pairs of tasks that are independent. Next line contains p pairs of letters, specifying independent tasks. Last line contains n letters — the sequence of tasks to be executed.

Выходные данные

On the first line of the output file print the minimal number of seconds needed to execute given tasks. On the second line print the number of essentially different ways to do so. On the third line print the number of exact ways.

Пример

Входные данные #1
8 2 2 1
AB
AABABBAB
Выходные данные #1
5
2
64
Источник Russian Teams Training Sessions in Petrozavodsk, Summer 2004, Andrew Stankevich Contest 8, Thursday, August 26, 2004