名前 (Name)

시간 제한1초메모리 제한1024 MB

요약

S와 T를 모두 부분 수열로 포함하면서 같은 문자가 두 번 나올 때 사이에 다른 문자가 K개 이상 오도록 하는 가장 짧은 이름의 길이를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열, 동적 계획법, 그리디, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

JOI 君と IOI 君は犬を飼うことにした．最初にすべきことは，犬の名前を決めることである．二人で話し合った結果，犬の名前を以下の 4 つの条件を満たすものにすることにした．

条件 1　名前は英大文字 (A, B, ..., Z) と英小文字 (a, b, ..., z) からなる文字列である．

条件 2　JOI 君の好きな文字列は長さ N の文字列 S であるから，S が名前の部分列となるようにする．

条件 3　IOI 君の好きな文字列は長さ M の文字列 T であるから，T が名前の部分列となるようにする．

条件 4　名前を呼びやすいものにするため，同じ文字の間には別の文字が K 文字以上あるようにする．厳密には，位置が異なる任意の同じ文字 2 つについて，必ずその間に別の文字が K 文字以上入っているようにする．なお，K = 0 の場合や，名前の文字がすべて異なる場合は，この条件を満たしていると考える．

ただし，これらの条件では英大文字と英小文字は区別される．例えば A と a は異なる文字とみなされることに注意せよ．

ここで，名前の部分列とは，名前から何文字か (0 文字でもよい) を取り除いて作れる文字列のことである．例えば，名前が algorithm であるとき，ai や lgtm は名前の部分列であるが，joi や logarithm は名前の部分列ではない．

二人は名前が短いほど良いと考えているため，4 つの条件のもとで最も短い名前を付けることにした．

JOI 君と IOI 君の好きな文字列および整数 K が与えられたとき，犬に付ける名前の文字数を求めるプログラムを作成せよ．

입력

入力は以下の形式で与えられる．

N   M   K
S
T

출력

犬に付ける名前の文字数を 1 行で出力せよ．

제한

1 ≦ N ≦ 500．
1 ≦ M ≦ 500．
0 ≦ K ≦ 3．
S は英大文字と英小文字からなる長さ N の文字列である．
T は英大文字と英小文字からなる長さ M の文字列である．
N, M, K は整数である．

예제6

예제 1
입력
```
10 10 0
hottokeiki
hottokeiki
```
예상 출력
```
10
```
예제 2
입력
```
10 10 1
hottokeiki
hottokeiki
```
예상 출력
```
11
```
예제 3
입력
```
10 10 3
hottokeiki
hottokeiki
```
예상 출력
```
15
```
예제 4
입력
```
6 9 0
Jouhou
Orinpikku
```
예상 출력
```
14
```
예제 5
입력
```
9 7 1
CoMMiTTee
TeRRaCe
```
예상 출력
```
15
```
예제 6
입력
```
6 8 2
JOIIOI
JOIGEGOI
```
예상 출력
```
9
```