ami nhận được mật mã người ngoài hành tinh. Mật mã người ngoài hành tinh được viết bằng ngôn ngữ ugnmouc. Để thuận tiện cho các bạn, ami đã dịch thứ ngôn ngữ khó hiểu này sang ngôn ngữ tiếng Anh là xâu \(S\). Ý nghĩa của mật mã này, các bạn không cần biết, các bạn chỉ cần kiểm tra xem mật mã này có ngon hay không.

Tiêu chuẩn ngon của người ngoài hành tinh cũng rất khác biệt. ami sẽ đưa cho các bạn một xâu khác, gọi là \(T\). Xâu \(S\) được xem là ngon nếu có thể chọn ra \(K \geq 1\) xâu con không giao nhau của \(S\), mỗi xâu đều có độ xài \(L\). Tạm gọi các xâu này là \(X_1, X_2, X_3, ..., X_K\), các xâu này phải có thứ tự từ điển nhỏ hơn hoặc bằng xâu \(T\) và \(K \geq C\). ami sẽ cho các bạn xâu \(S\), xâu \(T\) và số \(C\), các bạn cần đếm số lượng số \(L\) để có thể biến xâu \(S\) thành ngon.

Xâu \(X\) được gọi là xâu con của S nếu ta có thể xoá đi một vài kí tự đầu tiên và cuối cùng (có thể không xoá) của \(S\) và thu được xâu \(X\)

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(L_S, L_T,\) và \(C\) lần lượt là chiều dài xâu \(S, T\) và số \(C\).
• Dòng tiếp theo chứa xâu \(S\) có đúng \(L_S\) kí tự.
• Dòng cuối cùng chứa xâu \(T\) có đùng \(L_T\) kí tự.

Output

• In ra một số nguyên là số lượng số \(L\) thoả mãn để biến xâu S thành ngon.

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(L_S, L_T, C \leq 100000\).

Example

2 1 2
AA
Z 

1