Нареку лень придумывать третью задачу этого контеста, поэтому его друг Артур предложил использовать ChatGPT. ChatGPT сгенерировал \(n\) задач, каждая из которых состоит из \(m\) букв, и Нарек рассматривает их как \(n\) строк. Чтобы усложнить задачу, он комбинирует задачи, выбирая некоторые из \(n\) строк (возможно, ни одной) и располагая их без изменения порядка. Его шанс решить задачу определяется как \(score_n - score_c\), где \(score_n\) — счёт Нарека, а \(score_c\) — счёт ChatGPT.
Нарек вычисляет \(score_n\), изучая выбранную строку (он двигается слева направо). Изначально он ищет букву \(\texttt{«n»}\), после неё буквы \(\texttt{«a»}\), \(\texttt{«r»}\), \(\texttt{«e»}\) и \(\texttt{«k»}\). Найдя все вхождения этих букв, он увеличивает \(score_n\) на \(5\) и возобновляет поиск \(\texttt{«n»}\) (он не возвращается назад, а просто продолжает с того места, на котором остановился).
После того как Нарек закончит, ChatGPT просматривает строку и увеличивает \(score_c\) на \(1\) для каждой буквы \(\texttt{«n»}\), \(\texttt{«a»}\), \(\texttt{«r»}\), \(\texttt{«e»}\), или \(\texttt{«k»}\), которые Нарек не смог использовать. Обратите внимание, что если Нарек не смог завершить последнее вхождение, найдя все \(5\) букв, то использованные им буквы учитываются в счёте ChatGPT \(score_c\), а Нарек не получает никаких очков, если он не закончил поиск всех 5 букв.
Помогите Нареку максимизировать значение \(score_n - score_c\), выбрав наиболее оптимальное подмножество начальных строк.
Выходные данные
Для каждого набора входных данных выведите одно целое число: максимально возможное значение \(score_n - score_c\).
Примечание
В первом наборе входных данных один из оптимальных ответов — когда Нарек не выбирает ни одну из строк, поэтому ответ равен \(0\). В качестве альтернативы он может выбрать все строки. В этом случае полная строка становится «nnaarreekk». Нарек может выбрать первые появления всех букв и добавить к счету \(5\). Его соперник добавит по \(1\) за все вторые появления, что в сумме составит \(5\). Поэтому ответ будет \(5 - 5 = 0\).
В третьем наборе входных данных единственный оптимальный ответ — когда Нарек не выбирает строку. Обратите внимание, что если бы он выбрал строку, то не смог бы найти последнюю букву «k», поэтому его счёт остался бы на уровне \(0\), а не стал бы \(5\). Затем ChatGPT добавил бы \(4\) за \(4\) буквы, и разница счётов стала бы \(0 - 4 = -4\).
В последнем наборе входных данных Нареку нужно выбрать первую и последнюю строки. Поместив эти две строки рядом друг с другом, он получает «\({\color{red}{n}}rr{\color{red}{a}}{\color{red}{r}}{\color{red}{e}}{\color{red}{k}}{\color{red}{n}}k{\color{red}{a}}{\color{red}{r}}{\color{red}{e}}{\color{red}{k}}{\color{blue}{z}}\)». Нарек может выбрать буквы, отмеченные красным цветом, и добавить к своему счету \(10\). Так как буквы чёрного цвета, которые оставил Нарек, может забрать соперник (они используются в слове «Нарек»), то он прибавляет к счету все остальные буквы и получает счет \(3\). Таким образом, ответ составляет \(10 - 3 = 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2
nn
aa
rr
ee
kk
1 5
narek
1 4
nare
5 7
nrrarek
nrnekan
uuuuuuu
ppppppp
nkarekz
|
0
5
0
7
|