E. Обманщик
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В университете закончился первый семестр. Как известно, после конца первого семестра у студентов начинаются каникулы. На каникулах Нура решила вернуться в Вичкополис. В качестве скромного сувенира она привезла Лехе из Павлополиса колбасу длины m. Всем известно, что любую колбасу можно представить в виде строки из строчных латинских букв, длина которой равна длине колбасы.

Леха очень обрадовался подарку и сразу же съел колбасу. Но потом он понял, что это был достаточно нетактичный поступок, ведь колбаса была сувениром! Поэтому хакер сразу же направился в мясную лавку. К сожалению, в лавке нашлась лишь другая колбаса длины n. Однако Леха не расстроился и купил эту колбасу. Придя домой, он решил разрезать купленную колбасу на несколько частей и пронумеровать части начиная с 1 слева направо. Затем он хочет выбрать несколько частей и склеить их так, чтобы полученная колбаса была равна колбасе, которую подарила Нура. При этом хакер может склеить два куска между собой только тогда, когда номер левого меньше номера правого куска. Кроме этого, он знает, что если он склеит более x кусков, то Нура заметит, что он подменил сувенирную колбасу, и очень сильно расстроится. Конечно же Леха не хочет расстраивать девушку. Хакер просит вас узнать, удастся ли ему разрезать купленную им колбасу, а затем склеить некоторые из полученных частей так, чтобы Нура ничего не заметила.

Более формально, вам дано две строки s и t. Длина строки s равна n, длина строки t равна m. Требуется выбрать несколько попарно непересекающихся подстрок из s так, чтобы их конкатенация в том самом порядке, как эти подстроки идут в s, была равна строке t. Обозначим за f(s, t) минимальное количество подстрок, которые надо выбрать, чтобы их конкатенация была равна t. Если выбрать такие подстроки невозможно, то f(s, t) = ∞. Леха очень хочет узнать, правда ли, что f(s, t) ≤ x.

Входные данные

В первой строке находится одно целое число n (1 ≤ n ≤ 105) — длина колбасы, купленной Лехой, то есть длина строки s.

Во второй строке находится строка s длины n, состоящая из строчных букв латинского алфавита.

В третьей строке находится одно целое число m (1 ≤ m ≤ n) — длина колбасы, купленной Нурой, то есть длина строки t.

В четвертой строке находится строка t длины m, состоящая из строчных букв латинского алфавита.

В пятой строке находится одно целое число x (1 ≤ x ≤ 30) — максимальное количество кусков колбасы, которые может склеить Леха, чтобы Нура ничего не заподозрила.

Выходные данные

В единственной строке выведите «YES» (без кавычек), если Лехе удастся подделать колбасу так, чтобы Нура ничего не заметила. В противном случае следует вывести «NO» (без кавычек).

Примеры
Входные данные
9
hloyaygrt
6
loyyrt
3
Выходные данные
YES
Входные данные
9
hloyaygrt
6
loyyrt
2
Выходные данные
NO
Примечание

Рассмотрим первый пример.

В оптимальном ответе Леха должен разрезать купленную им самим колбасу следующим образом: hloyaygrt = h + loy + a + y + g + rt. Затем он нумерует полученные части от 1 до 6:

  • h — номер 1
  • loy — номер 2
  • a — номер 3
  • y — номер 4
  • g — номер 5
  • rt — номер 6

После чего хакер должен склеить части с номерами 2, 4 и 6 и получить колбасу loyyrt, равную той, что подарила Нура. Таким образом, ему придётся склеить три куска. Так как x = 3, то следует вывести «YES» (без кавычек).

Во втором примере обе колбасы совпадают с колбасами из первого примера. Однако, так как x = 2, то следует вывести «NO» (без кавычек).