题目描述

给定两个字符串 $s,t$，长度分别为 $n,m$。你需要选择 $s$ 的若干个两两不相交的子串，然后将它们按照原先在 $s$ 中出现的顺序合并起来，希望得到 $t$。

令 $f(s,t)$ 表示最少要选择的 $s$ 的子串数目，以便它们的并是串 $t$。如果无法合理选择这样的子串，则 $f(s,t)=+\infin$。现在我们想知道，对于给定的 $s,t$，是否有 $f(s,t)\leq x$。

输入格式

第一行一个整数 $n$，第二行一个长度为 $n$ 的字符串 $s$。

第三行一个整数 $m$，第四行一个长度为 $m$ 的字符串 $t$。

第五行一个整数 $x$。

$1 \le m\leq n \leq 10^5, 1\le x\leq 30$。

输出格式

在一行中输出 YES 或 NO 表示答案。

9
hloyaygrt
6
loyyrt
3

YES

9
hloyaygrt
6
loyyrt
2

NO