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.
输入解释
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）
输出解释
Print the number of editing operations in one line. If the answer is more than LIM, just output -1.