Вернувшись из леса, Алёна начала читать книгу. Ее взгляд упал на строки 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 — произвольная последовательность строк (возможно, пустых);
- сумма длин строк последовательности максимальна среди всех возможных вариантов.
Помогите Алёне справиться с непростой задачей и найти хотя бы суммарную длину строк искомой последовательности.
Подстрока строки — это непрерывная последовательность букв строки.
Выходные данные
В единственной строке выведите одно целое неотрицательное число — суммарную длину строк в искомой последовательности.
Гарантируется, что существует хотя бы одна искомая последовательность строк.