ОШ 2017 Группа B. Динамическое программирование - 0 - a, 1

Задача B. 0 - a, 1 - ab ≡

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

заменять символ 0 на строку из одного или более символов a
заменять символ 1 на строку из одного или более символов a, либо на строку из одного или более символов b

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

Первая строка входного файла содержит числа N M.

Вторая строка входного файла содержит строку s.

Третья строка входного файла содержит строку t.

Выходной файл должен содержать единственный символ Y или N.

1 ≤ N, M ≤ 10000

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 3 101 bab`	`Y`
2	`4 3 1001 bab`	`N`