第一学期结束了。你知道,第一学期结束后假期就开始了。假期里,努拉决定返回维克波利斯。作为给莱哈的一份朴素的纪念品,她从巴甫洛波利斯带来了一根米长的香肠。大家都知道,任何一根香肠都可以表示为一串小写英文字母,其长度等于香肠的长度。
Leha 对这份礼物非常满意,立即吃掉了香肠。但后来他意识到这是一个很不明智的行为,因为香肠是纪念品!于是黑客立即前往肉店。不幸的是,店里只有另一根长度为n的香肠。然而Leha并没有不高兴,买了这根香肠。回家后,他决定把买来的香肠切成几块,并从左到右从1开始编号。然后他想选择几块并将它们粘在一起,以便获得的香肠与Noora给的香肠相同。但只有当左边的碎片数量小于右边的碎片数量时,黑客才能将两块碎片粘在一起。此外,他知道如果他粘了超过 x 块,Noora 就会注意到他伪造了纪念品香肠,并且会非常沮丧。莱哈当然不想让女孩不高兴。黑客要求你查明他是否能够切开他买的香肠,然后粘上一些碎片,这样诺拉就不会注意到任何东西。
正式地,您将获得两个字符串 s 和 t。字符串s的长度为n,字符串t的长度为m。要求从s中选择几个两两不相交的子串,使得它们按照这些子串在s中出现的顺序串联起来,等于字符串t。用 f(s, t) 表示要选择的子字符串的最小数量,以便它们的串联等于字符串 t。如果不可能选择这样的子串,则 f(s, t) = ∞。 Leha 确实想知道 f(s, t) ≤ x 是否成立。
输入
第一行包含单个整数 n (1 ≤ n ≤ 105) — Leha 购买的香肠长度,即字符串 s 的长度。
第二行包含长度为n的由小写英文字母组成的字符串s。
第三行包含单个整数 m (1 ≤ m ≤ n) — Noora 购买的香肠长度,即字符串 t 的长度。
第四行包含长度为m的由小写英文字母组成的字符串t。
第五行包含单个整数 x (1 ≤ x ≤ 30) — Leha 可以粘合的香肠的最大数量,这样 Noora 就不会注意到任何东西。
输出
在唯一的一行中打印“YES”(不带引号),如果Leha能够成功地创建新香肠,这样Noora就不会注意到任何事情。否则打印“NO”(不带引号)。
示例
输入 #1
9 hloyaygrt 6 loyyrt 3
输出 #1
YES
输入 #2
9 hloyaygrt 6 loyyrt 2
输出 #2
NO
注意
让我们考虑第一个示例。
在最佳答案中,Leha 应该按照以下方式切他买的香肠:hloyaygrt = h + loy + a + y + g + rt。然后他将收到的零件从 1 编号到 6:
- h — 数字 1
- 洛伊 — 2 号
- a — 数字 3
- y — 数字 4
- g — 数字 5
- rt — 数字 6
因此,黑客应该将编号为 2、4 和 6 的部件粘合起来,并获得等于 Noora 给出的 1 的香肠 loyygrt。因此,他必须粘合三块。由于 x = 3 你应该打印“YES”(不带引号)。
在第二个样品中,两种香肠与第一个样品中的香肠一致。然而,由于 x = 2 你应该打印“NO”(不带引号)。