Подарки

Манао решил устроить вечеринку. Он ярко украсил свою хату, тщательно подобрал меню, созвал узкий круг друзей... и вдруг осознал, что забыл про подарки!

На своих вечеринках Манао всегда дарит гостям подарки. Более того, он всегда дарит каждому что-нибудь такое, чему тот будет рад. Сами гости тоже приносят подарки, каждый по одной штуке. Так как времени осталось немного, Манао не успеет накупить подарков, поэтому ему нужно найти способ выкрутиться из ситуации. И тогда его осеняет гениальная идея: перераспределить принесённые гостями подарки между ними! Естественно, отдать человеку принесённый им же подарок нельзя. Манао хорошо знает своих друзей и заранее может сказать, кому из них понравится принесённый кем подарок.

Но, к сожалению, может так случиться, что распределить подарки так, чтобы все друзья были рады, не получится. Поэтому Манао решился позвать вдобавок ещё некоторое количество знакомых. Манао хорошо знает и их, и поэтому может с уверенностью предсказать, кто что принесёт и чему будет рад. Обижать знакомых Манао тоже не хочет, поэтому каждый из них также должен получить подарок, которому будет рад. Но чтобы не превращать вечеринку в полный балаган, Манао пригласит наименьшее количество знакомых, которое обеспечит, что распределить подарки между всеми гостями так, чтобы каждый был рад, получится.

У Манао N друзей и M других знакомых. Пронумеруем друзей числами от 1 до N, а знакомых числами от N+1 до N+M. Вам дана матрица, по которой можно определить, чей подарок кому понравится. Определите наименьшее количество знакомых, которых надо дополнительно позвать. Если это невозможно, выведите число -1.

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

Первая строка входного файла содержит два числа N и M. Каждая из следующих N+M строк содержит по N+M символов "Y" или "N". j-ый символ в i-ой из этих строк обозначает, понравится ли человеку с номером i подарок человека с номером j.

2 ≤ N ≤ 100, 0 ≤ M ≤ 100. Ни одному гостю не может понравиться свой же подарок.

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

Выведите -1, если никакое множество знакомых не спасёт вечеринку Манао, и размер такого минимального множества в противном случае.

Примеры

Примечание

В первом примере можно пригласить человека с номером 3, а потом отдать гостю 2 подарок, принесённый гостем 3, гостю 3 подарок, принесённый гостем 1, а гостю 1 подарок гостя 2. В третьем примере можно, пригласив обоих знакомых, обменять подарки первого и второго друзей, четвертому отдать подарок третьего, третьему — пятого, а пятому — четвертого.