Mô tả và yêu cầu

An có hai xâu 𝑠, 𝑡 gồm các chữ cái Latin in thường và một số nguyên dương 𝑘. An
muốn chọn 𝑘 xâu con rời nhau khác rỗng gồm các ký tự liên tiếp trong xâu 𝑠 sao
cho các xâu này cũng xuất hiện rời nhau trong xâu 𝑡 với cùng một thứ tự trong xâu
𝑠 và tổng độ dài của 𝑘 xâu này là lớn nhất có thể.
Một cách cụ thể hơn, An muốn tìm 𝑘 xâu khác rỗng gồm 𝑝1, 𝑝2, … , 𝑝𝑘 sao cho:
 Xâu 𝑠 có thể biểu diễn bởi chuỗi 𝑎1𝑝1𝑎2𝑝2 … .𝑎𝑘𝑝𝑘𝑎𝑘+1 và xâu 𝑡 có thể
biểu diễn bởi chuỗi 𝑏1𝑝1𝑏2𝑝2 … 𝑏𝑘𝑝𝑘𝑏𝑘+1 trong đó 𝑎𝑖, 𝑏𝑖(𝑖 = 1 … 𝑘 + 1) là
một xâu bất kỳ (có thể là xâu rỗng) trong 𝑠 và 𝑡.
 |𝑝1| + |𝑝2| + ⋯ + |𝑝𝑘| đạt giá trị lớn nhất, với |𝑝𝑖| là độ dài của xâu 𝑝𝑖.
Bạn hãy giúp An tính toán tổng độ dài lớn nhất của 𝑘 xâu thỏa mãn yêu cầu bài
toán.
Dữ liệu: vào từ thiết bị nhập chuẩn:
 Dòng đầu tiên chứa 3 số nguyên dương 𝑛, 𝑚, 𝑘(1 ≤ 𝑛, 𝑚 ≤ 1000,1 ≤ 𝑘 ≤
10) trong đó 𝑛 là độ dài xâu 𝑠 và 𝑚 là độ dài xâu 𝑡;
 Dòng thứ hai chứa xâu s gồm các chữ cái in thường;
 Dòng thứ ba chưa xâu t gồm các chữ cái in thường.
Kết quả: ra thiết bị xuất chuẩn:
 Ghi ra một dòng là tổng độ dài lớn nhất của 𝑘 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 ra -1.

Ví dụ

INPUT                      OUTPUT

                      3 2 2
                      abc                             2
                      ab

                      9 12 4
                      bbaaababb                       7
                      abbbabbaaaba

                      3 3 3
                      abc                             -1
                      def

Giải thích: những xâu con được phân chia ở trong xâu 𝑠 và 𝑡 được đặt trong dấu
ngoặc vuông:
Ví dụ 1:  [a][b]c và [a][b] tổng độ dài bằng 2
Ví dụ 2: [bba][aa][b][a]bb và ab[bba]bb[aa]a[b][a] tổng độ dài bằng 7
Giới hạn:
      Subtask 1 (20% số test): 1      ≤  𝑘 ≤  𝑛, 𝑚  ≤  10
      Subtask 2 ( 30% số test): 1      ≤  𝑛, 𝑚  ≤  100,1   ≤  𝑘  ≤  10
      Subtask 3 ( 50% số test): 1      ≤  𝑛, 𝑚  ≤  1000,1    ≤  𝑘 ≤  10