Đề bài

Để giúp Dũng lấy lại gốc môn tin sau chuỗi ngày ăn chơi sa đọa, Hoành đã ra cho cậu bài toán như sau:

Hoành lấy ra hai xâu \(s\) và \(t\) gồm các ký tự latin thường cùng với một số nguyên \(k\). Hoành bảo Dũng hãy 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 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, Dũng phải tìm \(k\) xâu khác rỗng \(p_1, p_2, … , p_k\) sao cho:

• Xâu \(s\) có thể biểu diễn bởi chuỗi \(a_1p_1a_2p_2 … a_kp_ka_{k+1}\) và xâu \(t\) có thể biểu diễn thành chuỗi \(b_1p_1b_2p_2 \ldots b_kp_kb_{k+1}\) trong đó \(a_i, b_i\) là một xâu bất kỳ (có thể là xâu rỗng).
• Tổng độ dài của các xâu \(p_1, p_2, \ldots , p_k\) đạt giá trị lớn nhất.

Dũng bó tay với bài toán này, đành phải nhờ bạn. Bạn hãy giúp Dũng lấy lại kiến thức nhé.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương \(n, m, k\) (\(1 \leq n, m \leq 2000\), \(1 \leq k \leq 10\))
• \(n\): độ dài của xâu \(s\)
• \(m\): độ dài của xâu \(t\)
• \(k\): số xâu con cần tìm
• Dòng thứ hai chứa xâu \(s\) gồm \(n\) ký tự latin thường.
• Dòng thứ ba chứa xâu \(t\) gồm \(m\) ký tự latin thường.

Dữ liệu ra

• In ra một số nguyên duy nhất 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\).

Giới hạn

Sample Input 1

3 3 2
abc
ab

Sample Output 1

2

Sample Input 2

9 12 4
bbaaababb
abbabbaaaba

Sample Output 2

7

Sample Input 3

3 3 3
abc
def

Sample Output 3

-1

Giải thích

• Ở ví dụ thứ nhất, Dũng có thể tách thành \([a][b]c\) và \([a][b]\), tổng độ dài là \(2\).
• Ở ví dụ thứ hai, Dũng có thể tách thành \([bba][aa][b][a]bb\) và \(ab[bba]bb[aa]a[b][a]\), tổng độ dài là \(7\).

Hạn chế