Name

Time limit1sMemory limit1024 MB

Summary

Find the length of the shortest name that contains both S and T as subsequences, with equal letters at least K characters apart.

Level: Medium7 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

JOI and IOI have decided to keep a dog. The first thing to do is choose the dog's name. After discussing it, they decided the name must satisfy the following four conditions.

Condition 1 The name is a string made of uppercase English letters (A, B, ..., Z) and lowercase English letters (a, b, ..., z).

Condition 2 JOI's favorite string is a string S of length N, so S must be a subsequence of the name.

Condition 3 IOI's favorite string is a string T of length M, so T must be a subsequence of the name.

Condition 4 To keep the name easy to call, two equal characters must have at least K other characters between them. More precisely, for any two equal characters at different positions, at least K other characters must lie between them. If K = 0, or if all characters in the name are different, this condition is considered satisfied.

Letters are case-sensitive. For example, A and a are different characters.

A subsequence of the name is a string made by removing some characters (possibly zero) from the name. For example, if the name is algorithm, then ai and lgtm are subsequences, but joi and logarithm are not.

Both want the name to be as short as possible, so they chose the shortest name that satisfies all four conditions.

Input

The input is given in the following format.

N   M   K
S
T

Output

Print the number of characters in the dog's name on one line.

Constraints

$1 \le N \le 500$ .
$1 \le M \le 500$ .
$0 \le K \le 3$ .
S is a string of length N made of uppercase and lowercase English letters.
T is a string of length M made of uppercase and lowercase English letters.
N, M, and K are integers.

Examples5

Example 1
Input
```
10 10 0
hottokeiki
hottokeiki
```
Expected output
```
10
```
Example 2
Input
```
10 10 1
hottokeiki
hottokeiki
```
Expected output
```
11
```
Example 3
Input
```
10 10 3
hottokeiki
hottokeiki
```
Expected output
```
15
```
Example 4
Input
```
6 9 0
Jouhou
Orinpikku
```
Expected output
```
14
```
Example 5
Input
```
9 7 1
CoMMiTTee
TeRRaCe
```
Expected output
```
15
```