Gifts

Mana is planning a party. He's decorated his house, chosen the menu, and invited his closest friends. But he suddenly realizes he forgot about the gifts!

At his parties, Mana always gives gifts to his guests, ensuring each person receives something they'll love. The guests also bring gifts, each bringing one. With time running out, Mana can't buy gifts himself, so he devises a clever plan: redistribute the gifts brought by the guests among them! However, he can't give someone the gift they brought. Mana knows his friends well and can predict who will like which gift.

Unfortunately, it might not be possible to distribute the gifts in a way that makes everyone happy. So, Mana decides to invite some additional acquaintances. He knows them well too and can predict what they will bring and what they will like. Mana wants to ensure that each acquaintance also receives a gift they'll be happy with. To keep the party manageable, Mana will invite the fewest number of acquaintances needed to ensure all guests receive a suitable gift.

Mana has N friends and M acquaintances. Friends are numbered from 1 to N, and acquaintances from N+1 to N+M. You are given a matrix that indicates whose gift each person will like. Determine the minimum number of acquaintances Mana needs to invite. If it's impossible, output -1.

Input

The first line of the input contains two numbers N and M. Each of the following N+M lines contains N+M characters "Y" or "N". The j-th character in the i-th line indicates whether the person numbered i will like the gift from the person numbered j.

2 ≤ N ≤ 100, 0 ≤ M ≤ 100. No guest can like their own gift.

Output

Output -1 if no set of acquaintances can save Mana's party, otherwise output the size of the minimal set.

Examples

Note

In the first example, you can invite the person numbered 3, then give guest 2 the gift brought by guest 3, guest 3 the gift brought by guest 1, and guest 1 the gift from guest 2. In the third example, by inviting both acquaintances, you can swap the gifts of the first and second friends, give the fourth the gift of the third, the third the gift of the fifth, and the fifth the gift of the fourth.