An có hai xâu ~s, t~ gồm các kí tự Latin in thường và một số nguyên ~k~. An muốn chọn ra ~k~ xâu con rời nhau khác rỗng gồm các kí tự liên tiếp trong xâu ~s~ sao cho các xâu này cũng xuất hiện rời nhau trong xâu ~t~ với cùng một thứ tự như trong xâu ~s~ và tổng độ dài của ~k~ xâu này là lớn nhất có thể.

Một cách cụ thể hơn, An muốn tìm ~k~ xâu khác rỗng ~p_1, p_2, \dots, p_k~ sao cho:

• Xâu ~s~ có thể được biểu diễn bởi chuỗi ~x_0 p_1 x_1 p_2 x_2 \dots p_k x_k~ ở đó ~x_0, x_1, \dots, x_k~ là một xâu bất kì (có thể là xâu rỗng).
• Xâu ~t~ có thể được biểu diễn bởi chuỗi ~y_0 p_1 y_1 p_2 y_2 \dots p_k y_k~ ở đó ~y_0, y_1, \dots, y_k~ là một xâu bất kì (có thể là xâu rỗng).
• ~|p_1| + |p_2| + \dots + |p_k|~ đạt giá trị lớn nhất, ở đó ~|p_i|~ là độ dài của xâu ~p_i~.

Yêu cầu: Hãy giúp An tính toán tổng độ dài lớn nhất của ~k~ xâu thỏa mãn yêu cầu bài toán.

Input

• Dòng đầu tiên chứa số nguyên ~n, m, k~ (~1 \le n, m \le 1000, 1 \le k \le 10~) trong đó ~n~ là độ dài của xâu ~s~, ~m~ là độ dài của xâu ~t~.
• Dòng thứ hai chứa xâu ~s~ gồm các kí tự Latin in thường.
• Dòng thứ ba chứa xâu ~t~ gồm các kí tự Latin in thường.

Output

• Ghi ra một dòng là tổng độ dài lớn nhất của ~k~ xâu con thỏa mãn yêu cầu bài toán. Nếu không tồn tại cách tách xâu thỏa mãn thì đưa ra ~-1~.

Sample Input 1

3 2 2
abc
ab

Sample Output 1

2