이름

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

요약

S와 T를 부분 수열로 포함하면서 같은 문자 사이가 K개 이상 떨어진 가장 짧은 이름의 길이를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

JOI 군과 IOI 군은 개를 키기로 했다. 가장 먼저 할 일은 개의 이름을 정하는 것이다. 두 사람이 의논한 끝에, 이름은 다음 네 가지 조건을 만족하도록 하기로 했다.

조건 1 이름은 영어 대문자 (A, B, ..., Z)와 영어 소문자 (a, b, ..., z)로 이루어진 문자열이다.

조건 2 JOI 군이 좋아하는 문자열은 길이 N인 문자열 S이므로, S가 이름의 부분 수열이 되도록 한다.

조건 3 IOI 군이 좋아하는 문자열은 길이 M인 문자열 T이므로, T가 이름의 부분 수열이 되도록 한다.

조건 4 이름을 부르기 쉽게 하려고, 같은 문자 사이에는 다른 문자가 K개 이상 있어야 한다. 엄밀히 말해, 위치가 다른 임의의 같은 문자 두 개 사이에는 반드시 다른 문자가 K개 이상 들어 있어야 한다. K = 0이거나 이름의 문자가 모두 다르면 이 조건을 만족한다고 본다.

대소문자는 구별된다. 예를 들어 A와 a는 서로 다른 문자이다.

이름의 부분 수열이란, 이름에서 몇 글자(0글자도 가능)를 지워서 만들 수 있는 문자열을 말한다. 예를 들어 이름이 algorithm일 때 ai와 lgtm은 이름의 부분 수열이지만, joi와 logarithm은 아니다.

두 사람은 이름이 짧을수록 좋다고 생각하므로, 네 조건을 모두 만족하는 가장 짧은 이름을 붙이기로 했다.

입력

입력은 다음 형식으로 주어진다.

N   M   K
S
T

출력

개에게 붙일 이름의 글자 수를 한 줄에 출력한다.

제한

$1 \le N \le 500$ .
$1 \le M \le 500$ .
$0 \le K \le 3$ .
S는 영어 대문자와 영어 소문자로 이루어진 길이 N의 문자열이다.
T는 영어 대문자와 영어 소문자로 이루어진 길이 M의 문자열이다.
N, M, K는 정수이다.

예제5

예제 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
```