DNA Subsequence

Sanggeun is a computer scientist studying DNA sequences, and he wants to compute a constrained longest common subsequence of two strings.

Consider a word $w = a_1 a_2 \cdots a_r$ over an alphabet $\Sigma$ (each $a_i \in \Sigma$). A subsequence of $w$ is $x = a_{i_1} a_{i_2} \cdots a_{i_s}$ chosen by indices $1 \le i_1 < i_2 < \cdots < i_s \le r$. A subsequence in which $i_{j+1} = i_j + 1$ for every $j = 1, 2, \ldots, s-1$ (that is, characters taken from consecutive positions) is called a segment of $w$. For example, ove is a segment of lovely, while loly is a subsequence of lovely but not a segment.

A word that is a subsequence of both $w_1$ and $w_2$ is a common subsequence; the longest such word is a longest common subsequence. The empty word of length $0$ is always a common subsequence.

Now add the following restriction. The chosen common subsequence must be formed by concatenating, in order, common segments — blocks that occur contiguously in both words — and every common segment used must have length at least $K$. Equivalently, when the common subsequence is aligned against each word, every maximal run of consecutively matched characters must have length at least $K$.

For example, with $K = 3$ and the two words lovxxelyxxxxx and xxxxxxxlovely, the word lovely can be split into the two common segments lov (length $3$) and ely (length $3$), so it satisfies the condition. On the other hand, xxxxxxx cannot be split into common segments that are all of length at least $K = 3$, so it does not satisfy the condition.

Given the two words and $K$, write a program that finds the maximum possible length of a common subsequence satisfying the above condition.

The input consists of several test cases. The first line of each test case contains an integer $K$ ($1 \le K \le 100$). The next two lines each contain one string consisting only of lowercase letters. Each string has length between $1$ and $1000$, inclusive. The last line of the input contains a single $0$, which marks the end of the input.

For each test case, print on its own line the maximum length of a common subsequence that satisfies the condition. If there is no such common subsequence of positive length, print $0$.