AT_joig2024_e 名前 (Name)

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. ( $ 2 $ 点) $ S = T $ ， $ K = 0 $ ． 2. ( $ 7 $ 点) $ S = T $ ， $ K = 1 $ ． 3. ( $ 16 $ 点) $ S = T $ ． 4. ( $ 17 $ 点) $ K = 0 $ ． 5. ( $ 13 $ 点) $ K = 1 $ ， $ N \leqq 25 $ ， $ M \leqq 25 $ ． 6. ( $ 15 $ 点) $ K = 1 $ ． 7. ( $ 20 $ 点) $ K \leqq 2 $ ． 8. ( $ 10 $ 点) 追加の制約はない． ### Sample Explanation 1 JOI 君と IOI 君の好きな文字列はどちらも `hottokeiki` である．ここで，犬の名前を `hottokeiki` にすることを考える．これは以下のように $ 4 $ つの条件を満たす． - **条件 1:** 名前は英大文字と英小文字からなる． - **条件 2:** 文字列 $ S $ (`hottokeiki`) は犬の名前 `hottokeiki` の部分列である． - **条件 3:** 文字列 $ T $ (`hottokeiki`) は犬の名前 `hottokeiki` の部分列である． - **条件 4:** $ K = 0 $ なので，この条件は満たしている． また，これが $ 4 $ つの条件を満たす中で最も短い名前である．この文字数 $ 10 $ を出力する． この入力例は小課題 $ 1, 3, 4, 7, 8 $ の制約を満たす． ### Sample Explanation 2 入力例 $ 1 $ とは $ K $ の値のみが異なる． もし犬の名前を入力例 $ 1 $ と同じ `hottokeiki` にすれば，**条件 4** を満たさない．なぜなら， $ 2 $ つの `t` の間に文字が $ 1 $ 個もないからである． $ 4 $ つの条件を満たす最も短い名前として `hotNtokeiki` などが考えられる．この文字数 $ 11 $ を出力する． この入力例は小課題 $ 2, 3, 5, 6, 7, 8 $ の制約を満たす． ### Sample Explanation 3 入力例 $ 1, 2 $ とは $ K $ の値のみが異なる． もし犬の名前を入力例 $ 2 $ と同じ `hotNtokeiki` にすれば，**条件 4** を満たさない．なぜなら， $ 2 $ つの `t` の間に $ 1 $ 文字しかなく， $ 2 $ つの `k` の間に $ 2 $ 文字しかなく， $ 2 $ つの `i` の間に $ 1 $ 文字しかないからである． $ 4 $ つの条件を満たす最も短い名前として `hotarutokeiyuki` などが考えられる．この文字数 $ 15 $ を出力する． この入力例は小課題 $ 3, 8 $ の制約を満たす． ### Sample Explanation 4 JOI 君の好きな文字列は `Jouhou`，IOI 君の好きな文字列は `Orinpikku` である．ここで，犬の名前を `OJouhorinpikku` にすることを考える．これは以下のように $ 4 $ つの条件を満たす． - **条件 1:** 名前は英大文字と英小文字からなる． - **条件 2:** 文字列 $ S $ (`Jouhou`) は犬の名前 `OJouhorinpikku` の部分列である． - **条件 3:** 文字列 $ T $ (`Orinpikku`) は犬の名前 `OJouhorinpikku` の部分列である． - **条件 4:** $ K = 0 $ なので，この条件は満たしている． また，これが $ 4 $ つの条件を満たす中で最も短い名前のひとつである．この文字数 $ 14 $ を出力する．なお，英大文字と英小文字は区別されるため，`jouhorinpikku`（文字数 $ 13 $ ）などは条件を満たさない． この入力例は小課題 $ 4, 7, 8 $ の制約を満たす． ### Sample Explanation 5 $ 4 $ つの条件を満たす最も短い名前として `CoMaMiTeRTeRaCe` などが考えられる．この文字数 $ 15 $ を出力する． この入力例は小課題 $ 5, 6, 7, 8 $ の制約を満たす． ### Sample Explanation 6 $ 4 $ つの条件を満たす最も短い名前は `JOIGEIGOI` である．この文字数 $ 9 $ を出力する． この入力例は小課題 $ 7, 8 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 500 $ ． - $ 1 \leqq M \leqq 500 $ ． - $ 0 \leqq K \leqq 3 $ ． - $ S $ は英大文字と英小文字からなる長さ $ N $ の文字列である． - $ T $ は英大文字と英小文字からなる長さ $ M $ の文字列である． - $ N, M, K $ は整数である．