You are given 2 strings and you have to find the Longest  Common Subsequence between them provided you can change atmost K characters in first string.

40% Test Case contains  K=0

Input:-

First line contain string s

Second line contain string t

Third Line contain integer K.

Output:-

1 Integer - Maximum Length of Longest  Common Subsequence.

Constraint:-

1<=|s| ,|t|<=2000

0<=K<=5