Migrated from Lutece 2652 肥宅做错了什么

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

肥宅 A 想要给女神送礼物，最后含泪剁手给女神买了他最喜欢的番剧《小龙女家的小林女仆》中最喜欢的露科亚的手办。可惜由于某站的 VIP 购在运输过程中稍微磕碰了一下，露科亚裂成了 114514 块。肥宅向客服投诉无果，终究是一个人扛下了所有，把碎的手办给扔了。

高富帅男神 B 是肥宅的好兄弟，想要帮助肥宅 A。B 首先去某站的 VIP 购找了露科亚手办是否有余量，可惜已经卖光了。于是 B 为了兄弟情不惜牺牲自己怪盗基德的等身手办。

众所周知手办可以表示成一个字符串，代表手办从左到右每一部分的特征。B 首先将基德手办从左到右切割成若干份，等价于将原串切分成若干连续子串。 然后找到一些相似的部分，用 502 粘起来，等价于选取一些切分出来的子串拼接成一个新串。

由于 502 的粘合能力有限，当超过 $x$ 个部分连成整体后会散架。此外，考虑到美观问题，B 希望粘合时保留原基德手办相对样子，即切下时在左侧的部分不能粘到切下时在右侧的部分的右侧。

高富帅男神 B 害怕如果不能拼成露科亚就浪费自己的基德手办了，请你帮帮 B 判断基德手办能否拼成露科亚手办。

Input

第一行一个正整数 $n$，表示基德手办对应字符串的长度。 第二行一个字符串 $s$，表示基德手办对应的字符串。 第三行一个正整数 $m$，表示露科亚手办对应字符串的长度。 第四行一个字符串 $t$，表示露科亚手办对应的字符串。 第五行一个正整数 $x$，表示手办最多能由多少部分拼成。

Output

若可以用基德手办拼出来露科亚手办，输出 $\texttt{YES}$，否则输出 $\texttt{NO}$。

Samples

6
meaqua
3
mua
2

YES

10
yamatomaya
5
amita
3

NO

Constraints

$1\le m\le n\le 10^5$ $s,t$ 中字符串中只包含小写字母。 $1\le x\le 30$

Note

样例一中，B 将基德手办切分成 $\texttt{m|eaq|ua}$ 三部分，选择第一块和第三块粘起来，按原相对顺序拼成 $\texttt{mua}$。

样例二中，基德手办不存在特征为 $\texttt i$ 的部分，故无法拼成露科亚手办。

此题从左到右的方向是固定的，即不需要考虑用 $s$ 串切开后是否能拼成 $t$ 串的逆序串。

Resources

2021 UESTC ICPC Training for String and Search Algorithm