Matches

S and P are two strings consisting of lowercase letters of the English alphabet, with lengths N and M (N ≤ 10 000, M ≤ 1000, N ≥ M).

In string P, we can replace all the letters in a subsequence of choice with the character '?'. For example, if P is 'ababu', then, by replacing the subsequence 'bab', P becomes 'a???u'. The replaced characters must have consecutive positions. The cost of this operation is the number of modified characters, 3 in the example.

The number of matches of the modified P string in string S is the number of positions on which P matches in S. P matches in S on some position i ≤ N – M if any character from P on position 0 ≤ j < M matches the corresponding letter in S, more precisely, if P_j matches S_i+j (using 0-based indexing). A letter matches only itself, while the '?' character matches any letter.

What is the minimum cost of an operation made on P such that P has at least K matches in S?

Input Specification

The first two lines of the input will contain strings S and P. The third line contains the natural number K (K ≤ |S| – |P| + 1).

Output Specification

Print the minimum cost of one operation made on P such that P has at least K appearances in S.

Sample Input 1

1. abecanacc
2. abac
3. 2

download as text file

Output for Sample Input 1

1. 2

download as text file

Sample Input 2

1. ababaiubu
2. ababu
3. 3

download as text file

Output for Sample Input 2

1. 4

download as text file

Sample Input 3

1. xxxzzzyyy
2. babac
3. 4

download as text file

Output for Sample Input 3

1. 5

download as text file

Sample Input 4

1. abababa
2. ba
3. 2

download as text file

Output for Sample Input 4

1. 0

download as text file

Explanation

In Sample 1, if we replace 'ba', P becomes 'a??c' with two appearances in S:

abecanacc	← S
a??c-----	← first appearance
----a??c-	← second appearance

In Sample 2, if we replace 'babu' in P, we get 'a????' with three appearances in S:

ababaiubu	← S
a????----	← first appearance
--a????--	← second appearance
----a????	← third appearance

There is no solution replacing only three characters.

In Sample 3, replace all characters of P, and then there will be 5 appearances in S.

In Sample 4, there is no need to change anything, P appears three times in S.