06/04/2025 17:39:29

Рабочее место участника

Задачи

243. Вопль

Ограничения: время – 5s/10s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из

$N$ букв (всего в алфавите племени

$M$ букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово

$s_i$ (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага

$f_i$ единиц страха. Если в вопль входит несколько слов, то их "страшность" суммируется. Например, если вопль содержит слова

$s_i$ и

$s_j$ , то вопль вселяет

$f_i\ +\ f_j$ единиц страха. Если вопль содержит

$k$ экземпляров одного и того же

$i$ -го слова, то этот вопль вселяет

$k⋅f_i$ единиц страха.

Требуется по заданным

$N$ ,

$M$ , алфавиту и списку слов

$s_i$ составить максимально страшный вопль.

В первой строке записано три числа –

$N$ ,

$M$ и

$K\ (0\ <\ N\ ≤\ 100,\ 0\ <\ M\ <\ 25,\ 0\ ≤\ K\ ≤\ 100)$ , где

$K$ – количество страшных слов. В следующей строке записан алфавит – строка из

$M$ строчных латинских букв. Далее в

$K$ строках записана информация о словах – само слово и через пробел одно число

$f_i\ (0\ <\ f_i\ ≤\ 10000)$ , обозначающее страшность этого слова.

В выходной файл необходимо вывести страшность полученного вопля и на следующей строке – сам вопль.

Пример ввода

3 5 4
abcde
abc 10
ab 5
be 7
e 4

Пример вывода

16
abe

Источник: http://neerc.ifmo.ru/school/archive/

02/07/2007	Лето 2007 дорешивание ( 7E)
16/07/2007	Лето 2007 - 7 (E)
25/10/2008	Занятие 6 (D)
14/10/2014	Занятие 7 (A)
10/07/2023	Лето 2023-7 сложные (A)
07/03/2024	ДП (повторение) (проводит BOGAT) (B)
08/07/2024	Лето 2024-7 сложные (A)
29/11/2024	ICPC Bedolagi (проводит BOGAT) (B)