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

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

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