An ó 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,…,p_k sao cho:

• Xâu s có thể được biểu diễn bởi chuỗi a_1 p_1 a_2 p_2…a_k p_k a_(k+1) ở đó a_1,a_2,…,a_(k+1) 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 b_1 p_1 b_2 p_2…b_k p_k b_(k+1) ở đó b_1,b_2,…,b_(k+1) là một xâu bất kì (có thể là xâu rỗng).

• |p_1 |+|p_2 |+⋯+|p_k | đạt giá trị lớn nhất, ở đó |p_i | là độ dài của xâu p_i.

Bạn 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≤n,m≤1000,1≤k≤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

9 12 4
bbaaababb
abbbabbaaaba

Sample Output

7

Giới hạn

- Subtask 1 (20%): 1≤k≤n,m≤10. 
- Subtask 2 (30%): 1≤n,m≤100,1≤k≤10.
- Subtask 3 (50%): 1≤n,m≤1000,1≤k≤10.