Shortest Valid Dog Name

JOI and IOI have decided to name their new dog. They wish to choose the shortest possible name that satisfies the following conditions:

1. The name must consist only of uppercase and lowercase English letters.
2. The name must contain JOI’s favorite string S (of length \(N\)) as a subsequence.
3. The name must contain IOI’s favorite string T (of length \(M\)) as a subsequence.
4. For any two occurrences of the same character in the name, if their positions are \(i\) and \(j\) with \(i<j\), then there must be at least \(K\) other characters between them. In other words, the positions must satisfy \[ j-i-1\ge K. \] (Note that the check is performed for any pair of equal characters.)

All conditions are case‐sensitive (for example, A and a are considered different characters). A subsequence of a string is defined as a string obtained by deleting zero or more characters without changing the order of the remaining characters. For instance, if the string is algorithm, then both ai and lgtm are subsequences, while joi and logarithm are not.

Given the strings \(S\) and \(T\) together with the integer \(K\), find the length of the shortest name that satisfies all the above conditions.

Note on the spacing condition: When the same letter appears more than once in the name, extra characters may need to be inserted between the forced letters (those coming from S and T) to ensure that any two same letters have at least \(K\) characters between them. For example, if the forced sequence is AA and \(K=2\), then an optimal placement would be to put the two A's in positions 1 and 4, so the length becomes 4.

inputFormat

The input is given from standard input and consists of three lines:

1. The first line contains three integers \(N, M, K\) separated by spaces.
2. The second line contains the string S (of length \(N\)).
3. The third line contains the string T (of length \(M\)).

It is guaranteed that S and T contain only uppercase and lowercase English letters.

outputFormat

Output to standard output a single integer representing the length of the shortest valid name.

sample

3 3 2
ABA
ABA

4