Problem Description

During an ACM training team gathering, Shenchuan and ybs performed a song in KTV. However, when Shenchuan started singing after ybs, the singing score dropped from 90 to 60! ybs was very dissatisfied with this and requested help from 37Lament.

The original of the song are represented by a string T, Shenchuan's singing is represented by a string S.37Lament wants to change the string S at such way, that it can be found in T as a substring. All the changes should be the following: 37Lament chooses one position in the string S and replaces the symbol in this position with the question mark "?". 37Lament is sure that the question mark in comparison can play the role of an arbitrary symbol. For example, if he gets string S="ab?b" as a result, it will appear in T="aabrbb" as a substring

Guaranteed that the length of the string S doesn't exceed the length of the string T. Help the hacker to replace in S as few symbols as possible so that the result of the replacements can be found in T as a substring. The symbol "?" should be considered equal to any other symbol.

Input Format

The first line contains two integers n and m — the length of the string S and the length of the string T correspondingly.

The second line contains n lowercase English letters — string S.

The third line contains m lowercase English letters — string T.

Output Format

Print single integer k — the minimal number of symbols that need to be replaced.

Sample

input1

3 5
abc
xaybz

output1

2

intput2

4 10
abcd
ebceabazcd

output2

1

Hint

$1 \le n \le 1000, 1 \le m \le 1000$