Cho trước hai xâu ~S~, ~T~ chỉ gồm các chữ cái in thường và một số nguyên ~k~.

Yêu cầu: Hãy tìm dãy gồm ~k~ xâu con khác rỗng không trùng nhau ~p_1, p_2, \dots, p_k~ sao cho:

• Xâu ~S~ phân tích được thành ~a_1p_1a_2p_2\dots a_kp_ka_{k+1}~, trong đó ~a_1, a_2, \dots, a_{k+1}~ là các xâu con tùy ý (có thể là xâu rỗng);
• Xâu ~T~ phân tích được thành ~b_1p_1b_2p_2\dots b_kp_kb_{k+1}~, trong đó ~b_1, b_2, \dots, b_{k+1}~ là các xâu con tùy ý (có thể là xâu rỗng);
• Tổng chiều dài của các xâu ~p_i~ (~i=1 \dots k~) là lớn nhất.

Input

• Dòng đầu ghi ~n, m, k~ (~1 \le n, m \le 1000, 1 \le k \le 10~), ~n~ là chiều dài của xâu ~S~, ~m~ là chiều dài của xâu ~T~;
• Dòng thứ hai ghi xâu ~S~;
• Dòng thứ ba ghi xâu ~T~.

Output

• Gồm một dòng ghi tổng chiều dài của các xâu ~p_i~

Sample Input 1

3 4 2
abc
acbd

Sample Output 1

2

Sample Input 2

7 6 2
abcefde
acbdef

Sample Output 2

3