Contest Duration: - (local time) (300 minutes) Back to Home
L - Almost LCS /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

S を書き換えたあと、S の部分列かつ T の部分列であるような文字列のうち、最長のものの長さは最大で何文字になりますか？
ただし、文字列 x が文字列 y の部分列であるとは、y から 0 個以上の文字を取り除き、残りの文字を元の順序で連結することで x が得られることをいいます。

### 制約

• 1 \leq |S|, |T| \leq 1000
• 1 \leq K \leq 10
• S, T は英小文字からなる。

### 入力

S
T
K


### 入力例 1

strength
slang
1


### 出力例 1

4


### 入力例 2

asdbvaklwebjkalhakslhgweqwbq
obqweogkmawgjkoanboebeoqejkazxcnmvqse
10


### 出力例 2

19


Score : 6 points

### Problem Statement

You are given strings S and T consisting of lowercase English letters. You can do the following operation between 0 and K times: choose one of the characters of S and replace it with any lowercase English letter.

What is the length of the longest possible string that is a subsequence of S after the replacements and also a subsequence of T?
Here, a string x is said to be a subsequence of a string y if x can result from removing zero or more characters from y and concatenating the remaining strings without changing the order.

### Constraints

• 1 \leq |S|, |T| \leq 1000
• 1 \leq K \leq 10
• S and T consist of lowercase English letters.

### Input

Input is given from Standard Input in the following format:

S
T
K


### Sample Input 1

strength
slang
1


### Sample Output 1

4


By replacing the 3-rd character of S with l, slng becomes a subsequence of both S and T.

Since it is impossible to have a subsequence of both S and T of length 5 or longer, 4 should be printed.

### Sample Input 2

asdbvaklwebjkalhakslhgweqwbq
obqweogkmawgjkoanboebeoqejkazxcnmvqse
10


### Sample Output 2

19