| Codeforces Round 358 (Div. 2) |
|---|
| Закончено |
Вернувшись из леса, Алёна начала читать книгу. Ее взгляд упал на строки s и t, длины которых равняются n и m соответственно. Как обычно, Алёне быстро наскучило читать, и она решила переключить внимание на строки s и t, которые показались ей очень похожими.
У Алёны есть любимое целое положительное число k, но, так как она еще маленькая, k не превосходит 10. Девочка хочет выбрать k непересекающихся подстрок строки s, таких что они встречаются в строке t как непересекающиеся подстроки в том же порядке, что и в строке s, а их суммарная длина максимальна.
Формально, Алёна хочет найти последовательность из k непустых строк p1, p2, p3, ..., pk, такую что:
- строка s представима в виде конкатенации a1p1a2p2... akpkak + 1, где a1, a2, ..., ak + 1 — произвольная последовательность строк (возможно, пустых);
- строка t представима в виде конкатенации b1p1b2p2... bkpkbk + 1, где b1, b2, ..., bk + 1 — произвольная последовательность строк (возможно, пустых);
- сумма длин строк последовательности максимальна среди всех возможных вариантов.
Помогите Алёне справиться с непростой задачей и найти хотя бы суммарную длину строк искомой последовательности.
Подстрока строки — это непрерывная последовательность букв строки.
В первой строке входных данных содержатся три целых числа n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10) — длина строки s, длина строки t и любимое число Алёны соответственно.
Во второй строке входных данных содержится строка s, состоящая из строчных букв латинского алфавита.
В третьей строке входных данных задана строка t, состоящая из строчных букв латинского алфавита.
В единственной строке выведите одно целое неотрицательное число — суммарную длину строк в искомой последовательности.
Гарантируется, что существует хотя бы одна искомая последовательность строк.
3 2 2
abc
ab
2
9 12 4
bbaaababb
abbbabbaaaba
7
Картинка, поясняющая второй пример из условия:
