Problem Description

There are two strings: A and B. We define an editing operation as “Insert a character”, “Delete a character” or “Replace a character”.
So your task is to calculate how many editing operations do we need to make B become the substring of A? If the answer is more than the given limitation, just output -1.

Input

Multiple test cases.
There are 3 lines in each test case:
String A is given in the first line, and the length of A is from 0 to 1000000.
String B is given in the second line, and the length of B is from 0 to 1000.
In the third line, there is an integer LIM. （0<= LIM <=30）

Output

Print the number of editing operations in one line. If the answer is more than LIM, just output -1.

annealing
annual
3

1