D. Алёона ба тэмдэгт мөрүүд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ойгоос ирснийхээ дараа Алёона ном уншиж эхэлсэн. Тэр харгалзан $n$ болон $m$ урттай $s$ болон $t$ тэмдэгт мөрүүдийг анзаарсан. Ном унших нь уйтгартай байсан учир Алёона маш төстэй гэж бодсон $s$ болон $t$ тэмдэгт мөрүүдэд анхаарлаа хандуулахаар шийдсэн.

Алёонагийн дуртай тоо нь эерэг бүхэл тоон утга $k$ ба Алёона балчир учир $k$ нь $10$-с хэтрэхгүй. Охин $s$ тэмдэгт мөрөөс огтлолцохгүй $k$ ширхэг хоосон биш дэд тэмдэгт мөрүүдийг сонгохыг хүсч байна. Ингэж сонгохдоо эдгээр тэмдэгт мөрүүд нь $t$ тэмдэгт мөрд $s$ тэмдэгт мөрд байсан шиг дарааллаараа тохиолдох огтлолцохгүй дэд тэмдэгт мөрүүд байхаар сонгоно. Алёона эдгээр тэмдэгт мөрүүдийн урт нь боломжит бүх боломжоос хамгийн урт нь байхыг илүүд үзнэ.

Илүү тодорхой хэлбэл Алёона дараах нөхцөлүүдийг хангах $k$ хоосон биш тэмдэгт мөрүүдийн дараалал $p_{1}, p_{2}, p_{3}, ..., p_{k}$-г олохыг хүсч байна:

  • $s$ тэмдэгт мөрийг $a_{1}p_{1}a_{2}p_{2}... a_{k}p_{k}a_{k + 1}$ хэлхээ хэлбэрээр дүрсэлж болох, энд $a_{1}, a_{2}, ..., a_{k + 1}$ нь дурын тэмдэгт мөрүүд байна (эдгээрийн зарим нь хоосон байж болно).
  • $t$ тэмдэгт мөрийг $b_{1}p_{1}b_{2}p_{2}... b_{k}p_{k}b_{k + 1}$ хэлхээ хэлбэрээр дүрсэлж болох, энд $b_{1}, b_{2}, ..., b_{k + 1}$ нь дурын тэмдэгт мөрүүд байна (эдгээрийн зарим нь хоосон байж болно).
  • дараалал дахь тэмдэгт мөрүүдийн уртуудын нийлбэр нь боломжит хамгийн их байх.

Алёонад энэ төвөгтэй бодлогыг шийдэхэд нь туслана уу мөн шаардлагатай дарааллын тэмдэгт мөрүүдийн уртуудын нийлбэрийг олно уу.

Тэмдэгт мөрийн дэд тэмдэгт мөр гэдэг нь тэмдэгт мөрийн дараалласан тэмдэгтүүдийн дарааллыг хэлнэ.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $m$, $k$ ($1 ≤ n, m ≤ 1000$, $1 ≤ k ≤ 10$) байх ба харгалзан $s$ тэмдэгт мөрийн урт, $t$ тэмдэгт мөрийн урт болон Алёонагийн дуртай тоо байна.

Хоёр дахь мөрөнд Англи жижиг үсгүүдээс бүрдэх $s$ тэмдэгт мөр байна.

Гурав дахь мөрөнд Англи жижиг үсгүүдээс бүрдэх $t$ тэмдэгт мөр байна.

Гаралт

Шаардлагатай дарааллын тэмдэгт мөрүүдийн уртуудын нийлбэрийг илэрхийлэх эерэг бүхэл тоон утгыг нэг мөрөнд хэвлэ.

Ядаж нэг шаардлагатай дараалал оршин байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 2 2
abc
ab
Гаралт
2
Оролт
9 12 4
bbaaababb
abbbabbaaaba
Гаралт
7

Тэмдэглэл

Дараах зураг нь хоёр дахь жишээний хариултыг илэрхийлнэ:

Сэтгэгдлүүдийг ачааллаж байна...