Задача: D1 (2023). Нарезка текста

Сначала напомним, что расстояние Левенштейна между двумя строками s и t это минимальное число операций: "добавить символ", "удалить символ" и "изменить один символ на другой", которое нужно применить к строке s, чтобы получить строку t. Например, расстояние между строками s = aba и t = dac равняется 3: можно применить такую последовательность операций: aba → ab → ac → dac.
Длинный текст s был зачитан, записан и разрезан на несколько кусков. Затем каждый из кусков был распознан и преобразован обратно в текст - получился набор строк A. К сожалению, преобразования были неидеальными. В результате в текст могли добавиться или пропасть слова, также некоторые слова могли измениться на похожие.
Строка s и каждая строка из A имеет такие свойства: каждый символ в этих строках либо маленькая латинская буква, либо пробел. Никакая строка не может начинаться или заканчиваться на пробел, в строках не может быть двух пробелов подряд.
Ваша задача: разбить текст s на |A| частей (назовем это разбиение S) так, чтобы отличие между A и S было минимальным. Отличием двух наборов одинаковой длины A и S назовем значение \(\sum_{i=1}^{|A|}dist(A_i, S_i)\), где dist(Ai,Si) - расстояние Левенштейна между строками Ai и Si.
Важно, что разрезать текст вы можете только по пробелам, причем этот пробел не будет входить ни в один из отрезков (то есть он пропадает). То есть разбиение S можно описать количеством слов (подстрок между двумя пробелами или концами исходной строки) в каждой строке разбиения.
Для лучшего понимания, рассмотрим пример: Пусть текст s равен "when the imposter is sus". Также пусть преобразование через аудио дало нам набор A из двух строк: первая равняется "when composter", а вторая равняется "has bus". Тогда, если мы разделим текст s так, чтобы в первой строке было 3 слова, а во второй 2, то набор S будет равняться [when the imposter, is sus]. Тогда отличием наборов A и S будет значение dist(when the imposter, when composter) + dist(is sus, has bus). Посчитав расстояния Левенштейна, получим, что отличие равно 5 + 3 = 8.
В первой строке входных данных записано число t количество наборов входных данных. Затем идут описания наборов.
В первой строке набора дается одно число n количество слов в тексте s.
Во второй строке набора дается текст s, содержащий n слов.
В третьей строке содержится одно число |A| количество строк в разбиении.
Далее каждая строка из разбиения A описывается двумя строками ввода: в первой содержится количество слов в этой строке, а во второй сама строка.
Для каждого набора входных данных выведите |A| положительных чисел количество слов в данной строке вашего разбиения S. Также сумма этих чисел должна равняться количеству слов в строке s.
Оценка за каждый набор входных данных будет вычисляться по формуле 5·(jury_diff/participant_diff), где
participant_diff отличие A и разбиения участника, а jury_diff минимальное отличие, которое смогло получить жюри или участники. Оценкой за тест будет сумма оценок за все наборы входных
данных.
В этой задаче t = 6. Длина текста s в каждом наборе входных данных не превышает 1000. Оценка за этот тест: 30 баллов.

Примеры

1
5
when the imposter is sus
2
2
when composter
2
has bus

3 2

Ваш ответ: